Pagini recente » Cod sursa (job #2569010) | Cod sursa (job #783347) | Cod sursa (job #1028123) | Cod sursa (job #1701521) | Cod sursa (job #1584353)
#include <bits/stdc++.h>
using namespace std;
char a[1000001];
int d1[1000001];
int d2[1000001];
long long Manacher(int n)
{
long long Ret = 0;
int l = 1,r = 0;
for (int i = 1; i <= n; i++)
{
int k = i > r ? 0 : min(d1[r-i+l],r-i);
k++;
while (i+k <= n && i-k >= 1 && a[i+k] == a[i-k]) k++;
d1[i] = k--;
Ret += d1[i];
if (i+k > r)
r = i + k, l = i - k;
}
l = 1,r = 0;
for (int i = 1; i <= n; i++)
{
int k = i > r ? 0 : min(d2[r-i+l+1],r-i+1);
k++;
while (i+k-1 <= n && i - k >= 1 && a[i+k-1] == a[i-k]) k++;
d2[i] = --k;
Ret += d2[i];
if (i+k-1 > r)
l = i - k, r = i + k - 1;
}
return Ret;
}
int main()
{
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
gets(a+1);
printf("%lld",Manacher((int)strlen(a+1)));
}