Competitive Programing Problem Solutions/String/Z- Algorithm.cpp
vector<int> z_function(string s)
{
    int n = (int) s.length();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; ++i)
    {
        if (i <= r)
            z[i] = min (r - i + 1, z[i - l]);

//        debug(i,l,r,z[i]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            ++z[i];
//        debug(i,l,r,z[i]);
        if (i + z[i] - 1 > r)
            l = i, r = i + z[i] - 1;
    }
    return z;
}
///An element Z[i] of Z array stores length of the longest substring
///starting from str[i] which is also a prefix of str[0..n-1].
///The first entry of Z array is meaning less as complete string is always prefix of itself.
///Here Z[0]=0.

An element Z[i] of Z array stores length of the longest substring
starting from str[i] which is also a prefix of str[0..n-1].
The first entry of Z array is meaning less as complete string is always prefix of itself.
An element Z [ i ] of Z array stores length of the longest substring starting from str [ i ] which is also a prefix of str [ 0 .. n - 1 ] . The first entry of Z array is meaning less as complete string is always prefix of itself .
vector<int> z_function(string s)
{
    int n = (int) s.length();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; ++i)
    {
        if (i <= r)
            z[i] = min (r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            ++z[i];
        if (i + z[i] - 1 > r)
            l = i, r = i + z[i] - 1;
    }
    return z;
}
vector < int > z_function ( string s ) { int n = ( int ) s . length ( ) ; vector < int > z ( n ) ; for ( int i = 1 , l = 0 , r = 0 ; i < n ; ++ i ) { if ( i <= r ) z [ i ] = min ( r - i + 1 , z [ i - l ] ) ; while ( i + z [ i ] < n && s [ z [ i ] ] == s [ i + z [ i ] ] ) ++ z [ i ] ; if ( i + z [ i ] - 1 > r ) l = i , r = i + z [ i ] - 1 ; } return z ; }
An element Z[i] of Z array stores length of the longest substring
starting from str[i] which is also a prefix of str[0..n-1].
An element Z [ i ] of Z array stores length of the longest substring starting from str [ i ] which is also a prefix of str [ 0 .. n - 1 ] .
//        debug(i,l,r,z[i]);
 //        debug(i,l,r,z[i]);
