Pagini recente » Cod sursa (job #388991) | Cod sursa (job #1447661) | Cod sursa (job #59262) | Cod sursa (job #253893) | Cod sursa (job #3299093)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("pscpld.in");
ofstream fout ("pscpld.out");
const int nmax=2e6+5;
int manacher[nmax];
string s;
int main()
{
string t;
fin >> t;
for (int i=0; i<t.size(); i++)
{
s+='#';
s+=t[i];
}
s+='#';
int mij=-1;
for (int i=0; i<s.size(); i++)
{
if (mij!=-1 && mij+manacher[mij]-1>=i)
manacher[i]=min(manacher[2*mij-i],mij+manacher[mij]-i);
while (i+manacher[i]<s.size() && i-manacher[i]>=0 && s[i+manacher[i]]==s[i-manacher[i]])
manacher[i]++;
if (mij==-1 || i+manacher[i]>mij+manacher[mij])
mij=i;
}
long long rez=0;
for (int i=0; i<s.size(); i++)
{
if (manacher[i])
rez+=manacher[i]/2;
}
fout << rez;
return 0;
}