Cod sursa(job #149381)

Utilizator scvalexAlexandru Scvortov scvalex Data 5 martie 2008 17:39:10
Problema Prefix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

int T,
	M;
char text[1000003];

int pi[1000000];

int main(int argc, char *argv[]) {
	FILE *fi = fopen("prefix.in", "r");
	fscanf(fi, "%d", &T);
	FILE *fo = fopen("prefix.out", "w");
	while (T--) {
		fscanf(fi, "%s", text + 1);
		text[0] = ' ';
		
		M = strlen(text);

		/*for (int i(1); i < M; ++i)
			cout << text[i] << " ";
		cout << endl;*/

		pi[1] = 0;
		int k = 0;
		for (int q = 2; q < M; ++q) {
			while ((k > 0) && (text[k+1] != text[q])) 
				k = pi[k];
			if (text[k+1] == text[q])
				++k;
			pi[q] = k;
		}

		/*for (int i(1); i < M; ++i)
			cout << pi[i] << " ";
		cout << endl;*/

		int K(0);
		for (int i(1); i < M; ++i)
			if (pi[i] && (i % (i - pi[i]) == 0))
				K = i;
		fprintf(fo, "%d\n", K);
		//cout << K << endl;
	}
	fclose(fo);
	fclose(fi);

	return 0;
}