Pagini recente » Cod sursa (job #2768424) | Cod sursa (job #2026620) | Cod sursa (job #3139425) | Cod sursa (job #2501634) | Cod sursa (job #2262546)
#include <fstream>
#include <iostream>
#include <cstring>
#define DIM 1000005
using namespace std;
ifstream fi("pscpld.in");
ofstream fo("pscpld.out");
int n;
char C[DIM],A[2*DIM];
int dp[DIM],st,dr,mid;
long long rez;
int main()
{
fi>>C;
n=strlen(C);
for(int i=0;i<n;i++)
{
A[2*i+1]=C[i];
A[2*i]='*';
}
A[2*n]='*';
for(int i=1;i<=2*n;i++)
{
if(i<=dr)
dp[i]=min(dp[2*mid-i],dr-i);
for(;i+dp[i]+1<=2*n&&i-dp[i]-1>=0&&A[i+dp[i]+1]==A[i-dp[i]-1];dp[i]++);
if(i+dp[i]>dr)
dr=i+dp[i],mid=i;
rez+=(dp[i]+1)/2;
}
fo<<rez;
fi.close();
fo.close();
return 0;
}