Cod sursa(job #152840)

Utilizator amadaeusLucian Boca amadaeus Data 9 martie 2008 20:45:14
Problema Prefix Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <stdio.h>
#include <string.h>

#define NX 1000010

int N, T, pi[ NX ];
char A[ NX ];

void calc_pi() {
	int i, k;
	for( i = 1, k = pi[0] = -1; i <= N; pi[ i++ ] = ++k )
		while( A[i] != A[k+1] && k != -1 )
			k = pi[k];
}

void cit() {
	int i;

	for( scanf( "%d\n", &T ); T; T-- ) {
		memset( A, 0, sizeof(A) );
		A[0] = ' ';

		fgets( A + 1, sizeof( A ), stdin );
		N = strlen( A + 1 ) - 1;

		calc_pi();

		for( i = N; i; i-- )
			if( pi[i] > 0 && pi[i] % ( i - pi[i] ) == 0 )
				break;
          printf( "%d\n", i );
	}
}

int main() {
	freopen( "prefix.in", "r", stdin );
	freopen( "prefix.out", "w", stdout );

	cit();

	return 0;
}