Pagini recente » Cod sursa (job #1754716) | Cod sursa (job #732019) | Cod sursa (job #938475) | Cod sursa (job #1367902) | Cod sursa (job #1472859)
#include <stdio.h>
#include <string.h>
#define MAX_LEN 1000000
char s[MAX_LEN + 1];
int Z[MAX_LEN + 1];
inline int MIN(int X, int Y) {
return X < Y ? X : Y;
}
void buildZ(char *s, int length, int *sol) {
int l = 0, r = 0;
memset(Z, 0, length);
for (int i = 1; i < length; i++) {
if (i <= r) {
Z[i] = MIN(r - i + 1, Z[i - l]);
}
while (i + Z[i] < length && s[Z[i]] == s[i + Z[i]]) {
Z[i]++;
}
if (i + Z[i] - 1 > r) {
r = i + Z[i] - 1;
l = i;
}
if (*sol < (Z[i] / i) * i) {
*sol = Z[i] / i * i + i;
}
}
}
int main(void) {
int numTests;
int n;
int q;
FILE *f = fopen("prefix.in", "r");
FILE *g = fopen("prefix.out", "w");
fscanf(f, "%d\n", &numTests);
for (; numTests; numTests--) {
fgets(s, MAX_LEN + 1, f);
n = strlen(s) - 1;
q = 0;
buildZ(s, n, &q);
fprintf(g, "%d\n", q);
}
fclose(f);
fclose(g);
return 0;
}