Pagini recente » Cod sursa (job #1657791) | Cod sursa (job #1361824) | Cod sursa (job #797697) | Cod sursa (job #2721649) | Cod sursa (job #3293513)
#include<bits/stdc++.h>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
int p[2000005];
void manacher_odd(string s){
int n=s.size();
s='$'+s+'^';
int l=0, r=1;
for(int i=1; i<=n; i++){
p[i]=max(0, min(r-i, p[l+(r-i)]));
while(s[i-p[i]]==s[i+p[i]]){
p[i]++;
}
if(i+p[i]>r){
l=i-p[i];
r=i+p[i];
}
}
}
int main()
{
string s, t="";
in>>s;
for(auto c:s){
t.push_back('#');
t.push_back(c);
}
t.push_back('#');
manacher_odd(t);
long long sol=0;
for(int i=1; i<=t.size(); i++){
p[i]/=2;
sol+=p[i];
}
out<<sol;
return 0;
}