Pagini recente » Cod sursa (job #2551786) | Cod sursa (job #1908962) | Cod sursa (job #1327338) | Cod sursa (job #3271797) | Cod sursa (job #3245379)
#include <fstream>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
string s,s2;
int v[2000005];
int main()
{
fin >> s;
s2+='$';
for(int i=0;i<s.size();++i){
s2+='#';
s2+=s[i];
}
s2+='#';
s2+='@';
int sz=s2.size();
int center=0,right=0,mirror;
for(int i=1;i<sz;++i){
if(i<right){
mirror=2*center-i;
v[i]=min(v[mirror],right-i);
}
while(s2[i+1+v[i]]==s2[i-1-v[i]]){
v[i]++;
}
if(i+v[i]>right){
center=i;
right=i+v[i];
}
}
long long cnt=0;
for(int i=0;i<sz;++i){
if(v[i]>0){
cnt+=1LL*((v[i]-1)/2+1);
}
}
fout << cnt;
return 0;
}