IOICJ 31 Repeated String ( KMP )
Problem Description:
Given string S, find A with minimum length, such that S is equivalent to A being concatenated several times.
Constraints:
1≤T≤100
1≤|S|≤1e5
TL: 1000 ms
Sample Input:
3
ababab
aaabaaab
aaabaaa
Sample Output:
2
4
7
Solution:
Let's do KMP on string S:
fail[ i ] + 1 : length of longest common substring of S's prefix and S[ 0, i ]'s suffix, specially fail[ 0 ] = -1
Let us think about fail[ S.size() - 1 ] + 1 :
For example, S = "aabaabaab", where fail[ S.size() - 1 ] + 1 = 6 :
aabaabaab
___aabaabaab
We can observe that the substring where the other side is empty, is again a part of the other side, where the part on other side again matches this side ... therefore if the length of that part is divisible by S.size(), the answer A is that part.
#include <bits/stdc++.h> using namespace std; typedef vector< int > vi; signed main(){ ios::sync_with_stdio( 0 ); int T; cin >> T; for( int ti = 0; ti < T; ++ti ){ string seq; cin >> seq; vi fail( seq.size() ); int fptr = fail[ 0 ] = -1; for( int i = 1; i < seq.size(); ++i ){ while( fptr != -1 and seq[ fptr + 1 ] != seq[ i ] ) fptr = fail[ fptr ]; if( seq[ fptr + 1 ] == seq[ i ] ) ++fptr; fail[ i ] = fptr; } int ans = seq.size() - ( fail[ seq.size() -1 ] + 1 ); if( seq.size() % ans == 0 ) cout << ans << endl; else cout << seq.size() << endl; } return 0; }