Pagini recente » Cod sursa (job #498701) | Cod sursa (job #1093569) | Cod sursa (job #1433514) | Cod sursa (job #2748874) | Cod sursa (job #1510593)
#include <cstdio>
#include <algorithm>
using namespace std;
const int Nmax = 1000000;
char S[Nmax + 1];
char s[2 * Nmax + 2];
int Z[2 * Nmax + 2];
int main(void) {
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
int n, i;
int l, r;
long long answer;
gets(S);
fclose(stdin);
i = 0;
while (S[i] != '\0') {
s[2 * i] = '$';
s[2 * i + 1] = S[i];
i++;
}
s[2 * i] = '$';
n = 2 * i + 1;
l = r = 0;
answer = 0LL;
for (i = 1; i < n; i++) {
if (i <= r) {
Z[i] = min(Z[2 * l - i], r - i);
}
while ((i - Z[i] - 1 >= 0) && (i + Z[i] + 1 < n) && (s[i - Z[i] - 1] == s[i + Z[i] + 1])) {
Z[i]++;
}
if (i + Z[i] > r) {
r = i + Z[i];
l = i;
}
answer += (Z[i] + 1) / 2LL;
}
printf("%lld\n", answer);
fclose(stdout);
return 0;
}