Module: Prefix function, Z function


Problem

2 /10


prefix function

Theory Click to read/hide

After optimizing the prefix function (for details here ), we get the final algorithm with O(n) asymptotics:

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< /span>];
while (j > 0 && s[i] != s[j])
j = pi[j-1];
if (s[i] == s[j]) ++j;
pi[i] = j;
}
returnpi;
}

Problem

Given a non-empty string S whose length N does not exceed \(10^6\). We will assume that the elements of the string are numbered from 1 to N.
 
For each position of the i character in the string, we will be interested in the substring that ends at that position and matches some beginning of the whole string. Generally speaking, there will be several such substrings, at least two. The longest of them has the length i, we will not be interested in it. And we will be interested in the longest of the remaining such substrings (note that such a substring always exists — in the extreme case, if nothing else is found, an empty substring will do).
 
The value of the prefix function \(\pi[i]\) will be the length of this substring.
 
The prefix function is used in various string processing algorithms. In particular, it can be used to quickly solve the problem of finding the occurrence of one string in another ("search for a pattern in the text").
 
Required for all i from 1 to N to compute \(\pi[i] \).
 
Input
One string of length N, \(0 < N <= 10^6\), consisting of small Latin letters.
 
Output
Output N numbers — prefix function values ​​for each position, separated by spaces.
 

 

Examples
# Input Output
1 abracadabra 0 0 0 1 0 1 0 1 2 3 4

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!