Cod sursa(job #2460572)
Utilizator | Magirescu Tudor Frostfire | Data | 23 septembrie 2019 22:26:32 |
---|---|---|---|
Problema | Prefix | Scor | 80 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 1.02 kb |
#include <iostream>
#include <fstream>
#include <cstring>
#define NMAX 10000000
using namespace std;
ifstream f("prefix.in");
ofstream g("prefix.out");
int t, phi[NMAX+10];
char s[NMAX+10];
int main()
{
f >> t;
while(t--)
{ f >> s;
memset(phi, 0, sizeof(phi));
int i=1, j=0;
while(i < strlen(s))
{ if(s[i] == s[j])
{ j++;
phi[i] = j;
i++;
}
else
{ if(j) j = phi[j-1];
else i++;
}
}
//for(int i=0; i<strlen(s); i++) cout << phi[i] << ' ';
//cout << '\n';
bool ok = 0;
for(int i=strlen(s)-1; i>=0 && !ok; i--)
if(phi[i] && phi[i] % (i + 1 - phi[i]) == 0) g << i+1 << '\n', ok = 1;
if(!ok) g << 0 << '\n';
}
return 0;
}