0
$\begingroup$

I'm looking at the algorithm for the prefix function from here https://cp-algorithms.com/string/prefix-function.html :

vector<int> prefix_function(string s) {
    int n = (int)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 = pi[j-1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}

In the worst case the variable "j" within the while loop halves in value. Hence the time complexity should be O(n*log(n)) and not O(n)? What's wrong with my reasoning?

$\endgroup$
3
  • $\begingroup$ The idea is to apply amortized analysis instead of summing up the worst cases. Any good textbook should contain a detailed analysis of this. $\endgroup$
    – codeR
    Commented Jun 16 at 17:42
  • 1
    $\begingroup$ You are also wrong about the "halving". j can decrease by only 1 as well, take for example the string aaaaaaab $\endgroup$
    – EnEm
    Commented Jun 16 at 18:28
  • $\begingroup$ @EnEm oh right, i incorrectly thought that pi[j] is at most j/2 $\endgroup$ Commented Jun 16 at 19:15

1 Answer 1

2
$\begingroup$

I figured it out. j never goes negative and it increases by at most n times. Thus the while loop (which always decreases j) will run a lifetime total of not more than n times.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.