Pagini recente » Cod sursa (job #2031833) | Cod sursa (job #2428007) | Cod sursa (job #549222) | Cod sursa (job #1415160) | Cod sursa (job #2955522)
/**
Citim un string cu maxim 1 milion de carctere, doar litere
mici.
Afișăm vectorul razelor determinat din algoritmul lui
Manacher.
*/
#include <iostream>
#include <fstream>
using namespace std;
char q[1000001],s[2000010];
int rz[2000010];
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int main()
{
fin>>q;
int i,nc=0,l,r;
s[nc++]='#';
for(i=0;q[i];i++)
{
s[nc++]=q[i];
s[nc++]='#';
}
s[nc]=0;
l=r=-1;
for(i=0;i<nc;i++)
{
if(i>r)rz[i]=0;
else rz[i]=min(rz[l+r-i],r-i);
while(i-rz[i]>=0 && s[i-rz[i]]==s[i+rz[i]])
rz[i]++;
rz[i]--;
if(i+rz[i]>r) l=i-rz[i],r=i+rz[i];
}
long long sum=0;
for(i=0;i<nc;i++)sum+=(rz[i]+1)/2;
fout<<sum;
return 0;
}