Prefix Function (π Array)

The prefix function summarizes repeated beginnings at the end of every prefix of a string. For position i, π[i] is the length of the longest proper prefix of s[0..i] that is also a suffix of that same substring. A proper prefix is shorter than the entire substring; otherwise every answer would trivially be i+1.

This lesson constructs π for one string independently of pattern searching. It explains why a failed candidate can jump to a smaller border without trying every length. Borders, periods, and repeated units are important applications; KMP will use the same array in a separate lesson to scan a text efficiently.

Prerequisites: Introduction to String Algorithms; arrays, loops, and the definition of a border.

Build the idea

1. 1. Read an array entry as a length

   For s=ababaca, the prefix array is 0 0 1 2 3 0 1. At i=4 the processed prefix is ababa: its longest proper border is aba, of length 3. At i=5 the prefix becomes ababac and no nonempty prefix ends in c, so the answer is 0. At i=6, the single a is a border.

   π[i] is a length, not a character index. A border of length j occupies s[0..j), and the next character needed to extend it is s[j]. The one-character prefix has no nonempty proper border, so π[0]=0. An empty string has an empty π array.

2. 2. Try to extend the previous best border

   When processing i>0, start with j=π[i−1]. The last j characters before i equal the first j characters. If s[i]=s[j], appending that equal character extends the border to length j+1. No new border can be longer: deleting the final character from any new border leaves a border of the previous prefix, whose maximum length was j.

   For i=3 in ababaca, the previous border length is 1. Compare s[3]=b with s[1]=b and extend to 2. This reuses established equalities instead of comparing the first two characters again.

3. 3. Follow the border chain on a mismatch

   If s[i] differs from s[j], a smaller candidate may still work. Because the previous suffix equals the length-j prefix, every smaller useful candidate must itself be a border of that length-j prefix. Its longest proper border has length π[j−1]. Replace j with π[j−1], then compare again. Repeating this follows all possible border lengths in descending order without skipping a valid candidate.

   At i=5 in ababaca, j starts at 3. Compare c to s[3]=b: mismatch. Fall back to π[2]=1; compare c to s[1]=b: mismatch. Fall back to π[0]=0; c also differs from s[0]=a. Set π[5]=0. This concrete chain is 3→1→0, not 3→2→1→0. Length 2 was not a border of the previously matched block, so trying it would be wasted work.

4. 4. State the loop invariant and termination

   Before each comparison, j is a border length of the already processed prefix s[0..i), and all larger candidates have been ruled out. A mismatch replaces j by a strictly smaller border, preserving the invariant. When equality occurs, j+1 is the longest extendable candidate; when j=0 also fails, the only answer is zero.

   The condition j>0 must come before accessing π[j−1]. After the fallback loop, compare s[i] and s[j] once more: j may be zero, which still permits a one-character border. Forgetting that final comparison loses valid restarts such as the final a in ababaca.

5. 5. Explain why nested loops are linear

   The outer loop moves i forward once per character. The candidate length j increases by at most one per outer iteration, and every fallback decreases it by at least one. Across the entire run, total decreases cannot exceed accumulated increases, because j never becomes negative. Therefore there are only O(N) fallback iterations overall, even if one particular character causes several.

   For any nonempty string, the entire border chain can be listed by starting at π[N−1] and repeatedly taking π[length−1]. A repeated-unit application uses p=N−π[N−1]: if N is divisible by p, the string is repetitions of its length-p prefix; otherwise it has no shorter whole repeating unit. For ababab, π[5]=4, p=2, and the repeated unit is ab. The divisibility check matters: ababa has period 2 but is not a whole number of copies of ab.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<string>
#include<vector>
using namespace std;
vector<int>prefixFunction(const string&s){
    int n=static_cast<int>(s.size());
    vector<int>pi(n,0); // A one-character prefix has no nonempty proper border.
    for(int i=1;i<n;++i){
        int j=pi[i-1]; // First try extending the previous longest border.
        while(j>0&&s[i]!=s[j]){
            j=pi[j-1]; // Only borders of this border remain candidates.
        }
        if(s[i]==s[j]){
            ++j; // Even length zero may extend to a one-letter border.
        }
        pi[i]=j; // Length, not the index of the border's final character.
    }
    return pi;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    getline(cin,s); // Preserve spaces and allow an empty string.
    vector<int>pi=prefixFunction(s);
    for(int i=0;i<static_cast<int>(pi.size());++i){
        cout<<pi[i]<<(i+1==static_cast<int>(pi.size())?'\n':' ');
    }
    if(pi.empty()){
        cout<<'\n'; // The empty string has an empty array.
    }
}

Complexity analysis

O(N) time: at most one increment per character and O(N) total strict fallback decreases. O(N) space for π and the stored input; apart from the returned array and input, the computation uses O(1) auxiliary state.

Example input and output

One line containing s, possibly empty and including spaces, of length at most 1,000,000. Print π[0],…,π[N−1] separated by spaces. For an empty string print one blank line.

Input

ababaca

Output

0 0 1 2 3 0 1

The prefix ending at position 4 is ababa, whose longest proper border is aba. The following c destroys every nonempty candidate, while the last a restarts a border of length one.

Practical applications

Border enumeration, minimal whole repeating units, periodicity checks, prefix occurrence counting, and KMP failure links. This lesson computes the array itself; the next lesson applies it to a separate text.

Check your understanding

After a mismatch at candidate border length j>0, what is the next candidate length?

Put it into practice

Print every nonempty proper border length of the complete input string in increasing order.