Pagini recente » Cod sursa (job #1015450) | Cod sursa (job #2542748) | Cod sursa (job #2980300) | Cod sursa (job #2367684) | Cod sursa (job #638915)
Cod sursa(job #638915)
# include <cstdio>
# include <cstring>
const char *FIN = "pscpld.in", *FOU = "pscpld.out";
const int NAX = 1000111;
int V[NAX];
char S[NAX];
inline int min (int a, int b) {
return a < b ? a : b;
}
int main (void) {
fscanf (fopen (FIN, "r"), "%s", S + 1);
int N = strlen (S + 1);
int st = 1, dr = 1;
long long sol = 0;
for (int j = 1; j <= N; sol += V[j++] + 1)
if (j <= dr) {
V[j] = min (V[st + dr - j], dr - j);
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;
}
st = 1, dr = 2;
for (int j = 1; j < N; ++j) {
if (S[j] == S[j + 1]) {
if (j <= dr) {
V[j] = min (V[st + dr - j], dr - j - 1);
for (st = j - V[j], dr = j + V[j] + 1; st > 1 && dr < N && S[st - 1] == S[dr + 1]; --st, ++dr)
V[j] += 1;
} else {
for (dr = (st = j) + 1; st > 1 && dr < N && S[st - 1] == S[dr + 1]; --st, ++dr)
V[j] += 1;
}
sol += V[j] + 1;
} else V[j] = 0;
}
fprintf (fopen (FOU, "w"), "%lld", sol);
}