0w1

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