# CFR 432 D. Prefixes and Suffixes ( Z algorithm )

Problem - 432D - Codeforces

1 ≤ |S| ≤ 1e5

http://codeforces.com/blog/entry/3107

O( N )

```string seq;

void init(){
cin >> seq;
}

vi Z;

void compute_Z_value( vi &Z, const string &seq ){
Z = vi( seq.size() );
Z[ 0 ] = seq.size(); // usually people put 0
for( int i = 1, L = 0, R = 0; i < seq.size(); ++i ){
if( R < i ){
L = R = i;
while( R < seq.size() and seq[ R - L ] == seq[ R ] ) ++R;
Z[ i ] = R - L;
--R;
} else{
int k = i - L;
if( Z[ k ] < R - i + 1 ){
Z[ i ] = Z[ k ];
} else{
L = i;
while( R < seq.size() and seq[ R - L ] == seq[ R ] ) ++R;
Z[ i ] = R - L;
--R;
}
}
}
}

vp ans;

void preprocess(){
compute_Z_value( Z, seq );
vi ss( seq.size() + 1 );
for( int i = 0; i < Z.size(); ++i ){
++ss[ Z[ i ] ];
}
for( int i = seq.size() - 1; i >= 0; --i ){
ss[ i ] += ss[ i + 1 ];
}
for( int i = 1; i <= seq.size(); ++i ){
if( Z[ seq.size() - i ] == i ){
ans.emplace_back( i, ss[ i ] );
}
}
}

void solve(){
cout << ans.size() << endl;
for( int i = 0; i < ans.size(); ++i ){
cout << ans[ i ].first << " " << ans[ i ].second << endl;
}
}
```