Pagini recente » Cod sursa (job #257425) | Cod sursa (job #2247109) | Cod sursa (job #2767948) | Cod sursa (job #180546) | Cod sursa (job #3041645)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
///#include <tryhardmode>
///#include <GODMODE::ON>
///YOU KNOW IT'S NOT THE SAME
///AS IT WAS...
using namespace std;
#define cin fin
#define cout fout
ifstream fin ("pscpld.in");
ofstream fout ("pscpld.out");
const int NMAX=2e6+5;
int dp[NMAX];
string a;
string s;
int main()
{
int n,i,j,st=0,dr=0,dist=0;
long long kon=0;
cin>>a;
n=a.size();
s.push_back('*');
for(i=0;i<n;i++)
{
s.push_back(a[i]);
s.push_back('*');
}
n=s.size();
for(i=0;i<n;i++)
{
if(i>dr)
dist=1;
if(i<=dr)
dist=min(dp[st+dr-i],dr-i+1);
while(i+dist<n)
{
if(i-dist<0)
break;
if(s[i+dist]!=s[i-dist])
break;
dist++;
}
dp[i]=dist;
if(dr<i+dist-1)
{
st=i-dist+1;
dr=i+dist-1;
}
}
for(i=0;i<n;i++)
kon+=dp[i]/2;
cout<<kon;
return 0;
}