Pagini recente » Cod sursa (job #578518) | Cod sursa (job #386421) | Cod sursa (job #2729045) | Cod sursa (job #2693784) | Cod sursa (job #2841454)
#include <bits/stdc++.h>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
string s;
vector<int> manacher_odd(string s)
{
s='@'+s+'$';
int l=0,r=-1;
int n=s.size()-2;
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 vector<int>(begin(p)+1,end(p)-1);
}
vector<int> manacher_gen(string s)
{
string a="#";
for(char c:s)
a+=c+string("#");
vector<int> p=manacher_odd(a);
return vector<int>(begin(p)+1,end(p)-1);
}
int main()
{
in>>s;
long long ans=0;
vector<int> v=manacher_gen(s);
for(int x:v) ans+=x/2; out<<ans<<'\n';
return 0;
}