Pagini recente » Cod sursa (job #3337471) | Cod sursa (job #3321854) | Cod sursa (job #3320268) | Cod sursa (job #3343688) | Cod sursa (job #3305958)
#include <fstream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
int mana[2000004];
int main(){
string x1,s;
cin>>x1;
s="##";
for(int i=0;i<x1.size();i++){
s+=x1[i];
s+='#';
}
int bs=0;
for(int i=1;i<s.size();i++){
if(bs+mana[bs]>=i){
mana[i]=min( mana[bs-(i-bs)], bs+mana[bs]-i);
while(i+mana[i]+1<s.size() && i-mana[i]-1>=1 && s[i+mana[i]+1]== s[i-mana[i]-1]){
mana[i]++;
}
if(i+mana[i]>= bs+mana[bs])bs=i;
}
else{
mana[i]=0;
while(i+mana[i]+1<s.size() && i-mana[i]-1>=1 && s[i+mana[i]+1]==s[i-mana[i]-1]){
mana[i]++;
}
bs=i;
}
}
long long cnt=0;
for(int i=1;i<s.size();i++){
cnt+= (mana[i]+1)/2;
}
cout<<cnt;
}