Pagini recente » Cod sursa (job #2817488) | Cod sursa (job #2839747) | Cod sursa (job #3293468) | Cod sursa (job #2001896) | Cod sursa (job #1435559)
#include<fstream>
#include<string>
#include<vector>
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
const int N=1000003;
string s;
vector<int> d1(N), d2(N);
int i,n,l,r;
long long Rs;
int main()
{
cin>>s; n=s.size();
for (i=0,l=0,r=-1;i<n;i++){
int k=(i>r ? 1:min(r-i+1,d1[l+r-i]));
while (i-k>=0&&i+k<n&&s[i-k]==s[i+k])k++;
d1[i]=k;
if (i+k-1>r)l=i-k+1,r=i+k-1;
Rs+=d1[i];
}
for (i=0,l=0,r=-1;i<n;i++){
if (i==0||s[i-1]!=s[i])continue;
int k=(i>r ? 1 : min(r-i+1,d2[l+r-i+1]));
while (i-k-1>=0&&i+k<n&&s[i-k-1]==s[i+k])k++;
d2[i]=k;
if (i+d2[i]-1>r)l=i-d2[i],r=i+d2[i]-1;
Rs+=d2[i];
}
cout<<Rs;
return 0;
}