# IOICJ 35 Stamp Problem ( Z-value, Union Find )

Problem Description:
You are given a string S. You want to find minimum length of string A, such that you could print S with A stamped on a paper arbitrary times. When making a new stamp, it is allowed to cover part of the string on the paper iff they are identical. For example, "abaababa" can be printed with "aba" as:
1. aba
2. abaaba
3. abaababa

Constraints:
1≤T≤100
1≤n≤1e5

Sample Input:
3
8
abaababa
4
aabb
5
aaaaa

Sample Output:
3
4
1

Solution:
Let us first preprocess Z values:
Z[ i ] : maximum length of common prefix substring of S[ 0, ) and S[ i, )
Let's enumerate answer i from 1 to length( S ):
we know that i is valid iff Z[ length( S ) - 1 - i ] = i, which implies its end is safe,
and maximum length of continuous segment such that each Z value of those elements is less than i, is less than or equal to i + 1.
For example:
S = "abaababa",
Z = "80130301"
We know that i = 1 is not valid because segment Z[ 1, 2 ) is less than Z[ i ] and length 1, which implies that the rightmost x ( x < i ) with Z[ x ] >= Z[ i ] cannot cover it. However, i = 3 is valid because one of the longest target segment is Z[ 1, 3 ), which is length 2 and can be covered with this i = 3 stamp because Z[ 1 - 1 ] ≥ i, and such stamp is supported.

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = ( int ) 1e5 + 5;

int N;
string seq;

int Z[ MAXN ];

int fa[ MAXN ];
int size[ MAXN ];
int MAXSIZE;

void dsu_init(){
for( int i = 0; i < N; ++i ){
fa[ i ] = i;
size[ i ] = 1;
}
}

int find( int x ){
if( fa[ x ] == x ) return x;
return fa[ x ] = find( fa[ x ] );
}

int unite( int x, int y ){
int a = find( x );
int b = find( y );
if( a == b ) return 0;
if( not ( size[ a ] >= size[ b ] ) ) swap( a, b );
fa[ b ] = a;
size[ a ] += size[ b ];
return 1;
}

signed main(){
ios::sync_with_stdio( 0 );
int T; cin >> T;
for( int ti = 0; ti < T; ++ti ){
cin >> N;
cin >> seq;
for( int i = 1, L = 0, R = 0; i < seq.size(); ++i ){
if( R < i ){
L = R = i;
while( R < N and seq[ R ] == seq[ R - L ] ) ++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 < N and seq[ R ] == seq[ R - L ] ) ++R;
Z[ i ] = R - L;
--R;
}
}
}
vector< vector< int > > z2pos( N );
for( int i = 1; i < N; ++i ){
z2pos[ Z[ i ] ].emplace_back( i );
}
int ans = N;
dsu_init();
MAXSIZE = 0;
for( int i = 0; i + 1 < N; ++i ){
if( i == 1 ) MAXSIZE = max( MAXSIZE, 1 );
for( int j = 0; j < z2pos[ i ].size(); ++j ){
int p = z2pos[ i ][ j ];
if( p - 1 > 0 and Z[ p - 1 ] <= i ) unite( p - 1, p );
if( p + 1 < N and Z[ p + 1 ] <= i ) unite( p, p + 1 );
MAXSIZE = max( MAXSIZE, size[ find( p ) ] );
}
if( MAXSIZE + 1 <= i + 1 and Z[ N - ( i + 1 ) ] == i + 1 ){
ans = i + 1;
break;
}
}
cout << ans << endl;
}
return 0;
}
```