Pagini recente » Cod sursa (job #3335597) | Cod sursa (job #3305387) | Cod sursa (job #3321968) | Cod sursa (job #3321934) | Cod sursa (job #3305800)
#include <bits/stdc++.h>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
int l[2000001];
int main() {
string s;
in>>s;
string t="#";
for(int i=0; i<s.size();i++) {
t.push_back(s[i]);
t.push_back('#');
}
s=t;
int cen=0,mr=-1;
long long ans=0;
for(int i=0;i<s.size();i++) {
if(cen<i and i<mr) {
int mrr=2*cen-i;
l[i]=min(l[mrr],mr-i);
} else
l[i]=0;
while(i-l[i]-1>=0 and i+l[i]+1<s.size() and s[i-l[i]-1]==s[i+l[i]+1])
l[i]++;
if(i+l[i]>mr) {
mr=i+l[i];
cen=i;
}
ans+=l[i]/2+(s[i]!='#');
}
out<<ans<<"\n";
return 0;
}