Pagini recente » Cod sursa (job #701250) | Cod sursa (job #464354) | Cod sursa (job #1669579) | Cod sursa (job #1833056) | Cod sursa (job #1980963)
/**
Manacher Algorithm: O(n) time
*/
#include<bits/stdc++.h>
#define maxN 1000005
using namespace std;
int n,k,odd[maxN],even[maxN];
char s[maxN];
long long sol;
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
scanf("%s",s);
n=strlen(s);
int l=0,r=-1;
for(int i=0;i<n;i++)
{
if(i>r)
{
k=1;
}
else k=min(odd[l+r-i],r-i);
while((i+k)<n && (i-k)>=0 && s[i+k]==s[i-k]) k++;
odd[i]=k--;
if((i+k)>r)
{
r=i+k;
l=i-k;
}
}
l=0;
r=-1;
for(int i=0;i<n;i++)
{
if(i>r) k=1;
else
k=min(even[l+r-i+1],r-i+1)+1;
while((i+k-1)<n && (i-k)>=0 && s[i+k-1]==s[i-k]) k++;
// k--;
even[i]=--k;
if((i+k-1)>r)
{
l=i-k;
r=i+k-1;
}
}
for(int i=0;i<n;i++)
sol=sol+1LL*(odd[i]+even[i]);
printf("%lld\n",sol);
return 0;
}