Cod sursa(job #156914)

Utilizator cos_minBondane Cosmin cos_min Data 12 martie 2008 19:52:06
Problema Prefix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>
#include <string>
using namespace std;

#define in "prefix.in"
#define out "prefix.out"
#define dim 1000013

int T, N, K, S;
int Pi[dim];
char Aux[dim], A[dim];

int main()
{
    FILE *fin = fopen(in,"r");
    freopen(out,"w",stdout);
    
    fscanf(fin,"%d\n", &T);
    for ( ; T > 0; --T )
    {
        int maxim = 0;
        N = S = 0;
        fgets(Aux,dim-1,fin);
        while ( Aux[N] >= 'a' && Aux[N] <= 'z' ) A[N+1] = Aux[N], N++;
        
        for ( int i = 1; i <= N; i++ ) Pi[i] = 0;
        
        K = Pi[1] = 0;
        
        for ( int i = 2; i <= N; i++ )
        {
            while ( K && A[K+1] != A[i] ) K = Pi[K];
            if ( A[K+1] == A[i] ) ++K;
            Pi[i] = K;
        } 
        
        for ( int i = 2; i <= N; i++ )
            if ( Pi[i] > 0 && i%(i-Pi[i]) == 0 ) S = i;
        
        printf("%d\n", S);
    } 
}