Pagini recente » Cod sursa (job #2631678) | Cod sursa (job #1864973) | Cod sursa (job #3124644) | Cod sursa (job #1343541) | Cod sursa (job #1582518)
#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 ? 1 : min(d1[l+r-i]+1,r-i+1);
while (i+k <= n && i-k >= 1 && a[i+k] == a[i-k]) k++;
d1[i] = k--;
Ret += d1[i];
if (i+k > r)
l = i - k, r = i + k;
}
l = 1, r = 0;
for (int i = 1; i <= n; i++)
{
int k = i > r ? 1 : min (d2[l+r-i+1]+1,r-i+1+1);
while (i+k-i <= n && i-k >= 0 && 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("%ld",Manacher(strlen(a+1)));
}