Pagini recente » Cod sursa (job #1138559) | Cod sursa (job #749658) | Cod sursa (job #1204372) | Cod sursa (job #2106913) | Cod sursa (job #2101730)
#include <cstring>
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
const int NMax=2000005;
char A[NMax];
long long Sol ;
int N,r=2,c=1,x,dif,L[NMax];
void Read()
{
fin>>A;
N=strlen(A);
N=2*N+1;
L[0]=0;
L[1]=1;
}
void Solve()
{
for(int i=2;i<=N;i++)
{
x=2*c-i;
dif=r-i;
if(dif>0)
{
L[i]=min(L[x],dif);
}
while(((i+L[i])<N && (i-L[i])>0) && (((i+L[i]+1)%2==0) || (A[(i+L[i]+1)/2] == A[(i-L[i]-1)/2])))
{
L[i]++;
}
if(i+L[i]>r)
{
r=i+L[i];
c=i;
}
}
for(int i=1;i<N;i++)
{
if(L[i]%2==1)
Sol=Sol+L[i]/2+1;
else
Sol=Sol+L[i]/2;
}
fout<<Sol;
}
int main()
{
Read();
Solve();
return 0;
}