Pagini recente » Cod sursa (job #3316681) | Cod sursa (job #1505199) | Cod sursa (job #2120618) | Cod sursa (job #2768832) | Cod sursa (job #1957877)
// Manacher
#include <bits/stdc++.h>
#define maxN 1000005
using namespace std;
int n,i,idx,len[2*maxN];
char aux[maxN],str[2*maxN];
long long sol;
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
gets(aux+1);
n=strlen(aux+1);
for(i=1;i<=n;i++)
str[2*i-1]='$',str[2*i]=aux[i];
str[n=2*n+1]='$';
int idx=0;
int center=0;
for(i=1;i<=n;i++)
{
if(i<=idx)
len[i]=min(idx+1-i,len[center-(i-center)]);
while(i+len[i]<=n && i-len[i]>=1 && str[i+len[i]]==str[i-len[i]])
len[i]++;
if(i+len[i]-1>idx){
idx=i+len[i]-1;
center=i;
}
sol+=len[i]/2;
}
printf("%lld",sol);
return 0;
}