Cod sursa(job #87204)

Utilizator DastasIonescu Vlad Dastas Data 26 septembrie 2007 20:33:15
Problema Prefix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <cstdio>

const int maxl = 10000001;

FILE *in = fopen("prefix.in","r"), *out = fopen("prefix.out","w");

int t;
char a[maxl];

int pi[maxl];

int main()
{
    fscanf(in, "%d", &t);

    while ( t-- )
    {
        fscanf(in, "%s", a + 1);

        int k = 0;
        int max = 0;
        for ( int i = 2; a[i]; ++i )
        {
            while ( k > 0 && a[k + 1] != a[i] )
                k = pi[k];
            if ( a[k + 1] == a[i] )
                ++k;
            pi[i] = k;
            if ( pi[i] > 0 && i % (i - pi[i]) == 0 )
                max = i;
        }

//        int max = 0;
//        for ( int i = 2; a[i]; ++i )
//            if ( pi[i] > 0 && i % (i - pi[i]) == 0 )
//                max = i;

        fprintf(out, "%d\n", max);
    }

	return 0;
}