Decrement Instead Of Jump
vector<int> prefix_function(string s) {
int n = s.length();
vector<int> pi(n);
for (int i = 1; i < n; i++) {
int j = pi[i-1];
while (j > 0 && s[i] != s[j])
j = j - 1; // line 7: should be j = pi[j-1]
if (s[i] == s[j])
j++;
pi[i] = j;
}
return pi;
}
The fallback on line 7 decrements instead of jumping through the table. It still terminates and it still returns the right answer for "aabaaab" and for "abcabcd". Which input exposes it, and what does it return?
Sign in to answer questions and track your progress
Sign In