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;
}