Pagini recente » Cod sursa (job #2546568) | Cod sursa (job #1141637) | Cod sursa (job #720292) | Cod sursa (job #2570908) | Cod sursa (job #1880177)
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
char s[100000],t[100000];
int lps[100000],n;
void citire()
{
fgets(s,200000,stdin);
n=strlen(s);
for(int i=0;i<n;i++)
{
t[2*i+1]=s[i];
t[2*i]='#';
}
}
void manacher()
{
int c=0,dr=0;
lps[0]=0;
lps[1]=1;
for(int i=2;i<=2*n;i++)
{
int ii=c+(c-i);
if(i<dr)
{
if(dr-i<lps[ii])
lps[i]=dr-i;
else
lps[i]=lps[ii];
}
else
lps[i]=0;
while((i-lps[i]-1)>=0&&(i+lps[i]+1)<=2*n+1&&t[i-lps[i]-1]==t[i+lps[i]+1])
lps[i]++;
if(lps[i]+i>dr)
{
dr=i+lps[i];
c=i;
}
}
int S=0;
for(int i=1;i<=2*n-1;i++)
{
if(lps[i]%2==0)
S+=lps[i]/2;
else
S+=lps[i]/2+1;
}
printf("%d",S);
}
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
citire();
manacher();
//cout << "Hello world!" << endl;
return 0;
}