Pagini recente » Cod sursa (job #1777465) | Cod sursa (job #1579842) | Cod sursa (job #1533673) | Cod sursa (job #306632) | Cod sursa (job #2289120)
#include <fstream>
#include <iostream>
#include <cstring>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
int n;
char s[1000005],a[2*1000005];
int P[2*1000005],R,c;
long long rez;
int main()
{
f>>s;
n=strlen(s);
for(int i=0;i<n;i++)
{
a[2*i+1]=s[i];
a[2*i]='*';
}
a[2*n]='*';
for(int i=1;i<=2*n;i++)
{
if(i<=R)
P[i]=min(P[2*c-i],R-i);
for(;i+P[i]+1<=2*n&&i-P[i]-1>=0&&a[i+P[i]+1]==a[i-P[i]-1];P[i]++);
if(i+P[i]>R)
{R=i+P[i];
c=i;
}
rez+=(P[i]+1)/2;
}
g<<rez;
f.close();
g.close();
return 0;
}