Pagini recente » Cod sursa (job #1560330) | Cod sursa (job #2157232)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
char s[1000005],d[2000005];
int b[2000005],ct;
long long sol;
int main()
{ int i,n,ct=0,l,r,mid;
fin>>s;
n=strlen(s);
d[++ct]='A';
for(i=0;i<n;++i)
{ d[++ct]=s[i];
d[++ct]='A';
}
l=r=mid=1;
for(i=2;i<=ct;++i)
{ if(i>r) l=r=mid=i;
else
{
b[i]=b[2*mid-i];
if(b[i]+i>=r)
{ b[i]=r-i;
mid=i;
l=mid-b[i];
}
}
while(l-1>=1 && r+1<=ct && d[l-1]==d[r+1])
{ b[mid]++;
l--; r++;
}
}
for(i=1;i<=ct;++i)
if(i%2)
sol=sol+b[i]/2;
else sol=sol+b[i]/2+1;
fout<<sol;
return 0;
}