Nu aveti permisiuni pentru a descarca fisierul grader_test10.ok
Cod sursa(job #1461)
Utilizator | Victor Rusu victorsb | Data | 13 decembrie 2006 18:56:26 |
---|---|---|---|
Problema | Prefix | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.81 kb |
#include <cstdio>
#include <string.h>
#define Lmax 1000001
char sir[Lmax];
int pref[Lmax],i,j,n;
void calcpref()
{
int m=strlen(sir),k=0,q,i;
pref[1]=0;
for (q=2;q<=m;q++)
{
while (k>0&&sir[k]!=sir[q-1])
k=pref[k];
if (sir[k]==sir[q-1])
k++;
pref[q]=k;
}
}
void solve()
{
int i,max=0;
for (i=strlen(sir);i>=1;i--)
if ( pref[i] > 0 )
if (i % (i-pref[i]) == 0 )
{
max=i;
break;
}
printf("%d\n",max);
}
int main()
{
freopen("prefix.in","r",stdin);
freopen("prefix.out","w",stdout);
scanf("%d\n",&n);
for (i=1;i<=n;i++)
{
scanf("%s\n",&sir);
calcpref();
solve();
}
return 0;
}