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; }