Pagini recente » Cod sursa (job #2090611) | Cod sursa (job #383446) | Cod sursa (job #479141) | Cod sursa (job #347919) | Cod sursa (job #2409499)
#include <bits/stdc++.h>
#define maxN 1000002
using namespace std;
FILE *fin = freopen("pscpld.in", "r", stdin);
FILE *fout = freopen("pscpld.out", "w", stdout);
char a[maxN], s[2 * maxN];
int p[maxN * 2];
long long ans;
void Manacher(int n)
{
int N = 2 * n + 1, r = 0, c = 0;
for (int i = 1; i < N; ++ i)
{
int ii = 2 * c - i;
if (r > i)
p[i] = min(r - i, p[ii]);
/// r = i + p[i], pos = 2 * i - i - p[i] - 1 (2 * i - r - 1)
while (s[i - p[i] - 1] == s[i + p[i] + 1])
++ p[i];
if (i + p[i] > r)
{
c = i;
r = i + p[i];
}
ans += (p[i] + 1) / 2;
// ans = max(ans, p[i]);
}
}
int main()
{
scanf("%s\n", a);
int n = strlen(a);
s[2 * n + 1] = '*';
for (int i = 0; i < n; ++ i)
{
s[i * 2] = '#';
s[i * 2 + 1] = a[i];
}
s[2 * n] = '#';
Manacher(n);
printf("%lld\n", ans);
return 0;
}