Pagini recente » Cod sursa (job #1137376) | Cod sursa (job #2742022) | Cod sursa (job #2490638) | Cod sursa (job #2874006) | Cod sursa (job #3293509)
#include<bits/stdc++.h>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
vector<int> manacher_odd(string s){
int n=s.size();
s='$'+s+'^';
int l=0, r=1;
vector<int> p(n+2);
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];
}
}
return p;
}
int main()
{
string s, t="";
in>>s;
for(auto c:s){
t=t+'#'+c;
}
t+='#';
vector<int> d=manacher_odd(t);
long long sol=0;
for(int i=1; i<=t.size(); i++){
d[i]/=2;
sol+=d[i];
}
out<<sol;
return 0;
}