Cod sursa(job #73877)

Utilizator vlad_popaVlad Popa vlad_popa Data 21 iulie 2007 14:04:10
Problema Prefix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
using namespace std;

#include <cstdio>
#include <cassert>
#include <string>
#include <sstream>
#include <algorithm>
#include <iostream>

#define FIN "prefix.in"
#define FOUT "prefix.out"
#define NMAX 1000001
#define CLEAR(X) memset ((X), 0, sizeof(X))
#define a(i) (s[i - 1])

char s[NMAX];
int N, pi[NMAX];

void prefix ()
{
    int k = 0;
    
    for (int i = 2; i <= N; ++ i)
    {
        while (k > 0 && a(k + 1) != a(i))
            k = pi[k];

        if (a(k + 1) == a(i))
            ++ k;
        pi[i] = k;
    }
}

void solve ()
{
     CLEAR (pi);
     
     prefix ();
     
     int K;
     for (K = N; K >= 1; -- K)
         if (pi[K] > 0 && K % (K - pi[K]) == 0)
            break;
            
     printf ("%d\n", K);               
}

void read ()
{
     int T;
     scanf ("%d\n", &T);
     
     while (T--)
     {
           gets (s);
           N = strlen (s) + 1;
           
           solve ();
     }
}

int
 main ()
{
      freopen (FIN, "rt", stdin);
      freopen (FOUT, "wt", stdout);
      
      read ();
      
      return 0;
}