0w1

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