Cod sursa(job #39484)
#include<stdio.h>
#include<string.h>
char x[1000005];
long pi[1000005],k,i,n,q,m,j,t,la,aux,max,matrix;
int main()
{
freopen("prefix.in","r",stdin);
freopen("prefix.out","w",stdout);
scanf("%ld",&t);
for(j=1;j<=t;j++)
{
scanf("%s",&x);
n=strlen(x);
for(i=n-1;i>=0;i--)
x[i+1]=x[i];
n++;
k=0;
for(i=2;i<n;i++)
{
while(k>0&&x[k+1]!=x[i])
k=pi[k];
if (x[k+1]==x[i])
k++;
pi[i]=k;
}
i=1;
max=0;
while (i<n)
{
aux=1;
la=i;
matrix=i-1;
while (pi[la]>=aux)
{
la++;
aux++;
if (aux-pi[la]==1) {matrix++;aux--;}
}
if (matrix)
if ((max<la-i+matrix-((la-i+matrix)%matrix))&&(la-i>=matrix)) max=la-i+matrix-((la-i+matrix)%matrix);
i=la+1;
}
printf("%ld\n",max);
}
return 0;
}