Pagini recente » Cod sursa (job #1498551) | Cod sursa (job #1816674) | Cod sursa (job #1066865) | Cod sursa (job #296582) | Cod sursa (job #638907)
Cod sursa(job #638907)
# include <cstdio>
# include <cstring>
const char *FIN = "pscpld.in", *FOU = "pscpld.out";
const int NAX = 1000005;
int V[NAX];
char S[NAX];
inline int min (int a, int b) {
return a < b ? a : b;
}
inline int calc (int N) {
return N - 1;
}
int main (void) {
fscanf (fopen (FIN, "r"), "%s", S + 1);
int N = strlen (S + 1);
int st = 1, dr = 1, sol = N;
for (int j = 2; j <= N; ++j)
if (j <= dr) {
V[j] = min (V[st + dr - j], dr - j);
if (j + V[j] == dr)
for (st = j - V[j], dr = j + V[j]; st > 1 && dr < N && S[st - 1] == S[dr + 1]; --st, ++dr)
V[j] += 1;
} else {
for (st = dr = j; st > 1 && dr < N && S[st - 1] == S[dr + 1]; --st, ++dr)
V[j] += 1;
}
for (int i = 1; i <= N; ++i)
sol += calc (V[i] * 2 + 1);
fprintf (fopen (FOU, "w"), "%d", sol);
}