Problem Link

Submission Link

Part 1: Calculate the Prefix function (next array) in $$$O(n)$$$

We can calculate the prefix function (next array) in linear time using the following code:

//next is a 0-indexed array that is initialized to zero.
//s is a 0-indexed string
for(int i = 1, j = 0; i < n; ++i){
    while(j && s[i] != s[j]) j = next[j-1];
    if(s[i] == s[j]) j++;
    next[i] = j;
}

While is it $$$O(n)$$$? The key idea is the amortized analysis. $$$j$$$ increases $$$n$$$ times, each times increase at most $$$1$$$ (in fact $$$0$$$ or $$$1$$$, $$$0$$$ if s[i] != s[j] and $$$1$$$ if s[i] == s[j]). Therefore, $$$j$$$ increases at most $$$n$$$. Since $$$j$$$ is never a negative number (you can prove it by induction on the next array), the amount $$$j$$$ decreases $$$\leq$$$ the amount $$$j$$$ increases $$$\leq n$$$. Each times $$$j$$$ decreases at least $$$1$$$ (as $$$next[j-1] \leq j-1$$$), so $$$j$$$ decreases at most $$$n$$$ times. To sum all, $$$j$$$ increases and decreases at most $$$2n$$$ times, which is $$$O(n)$$$.

But there is a trap! We can calculate the whole next array in $$$O(n)$$$, but for a suffix of length $$$k$$$, calculating the items of the next array that corresponds with that suffix is not $$$O(k)$$$!!! In fact, the worst complexity for every suffix, even a single character, could also be $$$O(n)$$$! In fact the example is very easy to construct: aaaaa....az, the next array is:

$$$[0, 1, ..., num(a)-1, 0]$$$.

For $$$0 \leq i \leq num(a)$$$, the line j = next[j-1] executes $$$0$$$ times, and when the index comes to $$$z$$$, j = next[j-1] would execute $$$num(a)$$$ times! That means, the computational burden on the suffix could also be $$$O(n)$$$!

The GrandLisboa earns $$$100$$$ million from $$$10$$$ gamblers, it may earn $$$90$$$ million from you and $$$10$$$ million from another $$$9$$$ gamblers, that is amortization! Let's come back to this problem. When you append each suffix $$$t$$$ to the original string $$$s$$$, the complexity to handle the suffix is not $$$O(|t|)$$$, in fact the worst case is $$$O(|s|)$$$, and according to the analysis above, such suffix is very easy to construct!

Part 2: A fix

We note that most next transition is unnecessary. For example,the $$$0$$$-indexed string $$$s$$$ is ababcababa and we are now checking the last character, which is a. it is not necessary to scan abab (length=$4$) at all, because the prefix abab (s[0:4]) is followed by c while the prefix abab (s[5:9]) is followed by a. So, scan the first two characters ab is enough! Inspired by this, we define a last array:

//last[i][c]: Among 0 <= k <= i such that [0...k] is a prefix of [0,...,i] and [i-k,...,i] is a suffix of [0,...,i], the max k such that s[k+1]==c
//For example, s = "abcabaabd", last[7]['d'] = 7, last[7][c] = 1.
//s[0:1] = "ab" is a prefix of s[0:7]("abcabaab").
//s[0:1] is also a suffix of s[0:7]
//and s[1+1] = s[2] = 'c'
//The transition function: last[i][c] = (c == s[i+1] ? (next[i] >= 1 ? last[next[i]-1][c] : -1) : i);

We can easily transfer to the proper place in $$$O(1)$$$ time. Deducing last[i][c] from last[i-1][*] costs $$$O(|\alpha|)$$$ time ($$$\alpha$$$ is the alphabet), and such transition only happens $$$O(n)$$$ times, so we can fix this issue in $$$O(n |\alpha|)$$$ time.

Part 3: Why don't us generalize this idea to the original KMP algorithm?

(1)The original $$$KMP$$$ algorithm is already linear and achieves the best theoretical complexity.

(2)The character set in the original $$$KMP$$$ algorithm is not restricted to the lower Latin letters. It can handle arbitrary character sets in linear time, not depending on the size of the character sets.