Pagini recente » Cod sursa (job #1071355) | Cod sursa (job #1177574) | Cod sursa (job #2982413) | Cod sursa (job #641456) | Cod sursa (job #3250049)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
vector<int> manacher_odd(string s) {
int n=s.size();
s="$"+s+"^";
vector<int> p(n + 2);
int l=1,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];
}
}
return vector<int>(begin(p), end(p));
}
vector<int> manacher(string s) {
string t;
for(auto c: s) {
t+=string("#")+c;
}
auto res=manacher_odd(t+"#");
return vector<int>(begin(res) + 1, end(res) - 1);
}
int main(){
string s;
fin>>s;
vector<int> ans=manacher(s);
int ans1=0;
for(auto i:ans){
ans1+=i/2;
}
fout<<ans1;
}