Pagini recente » Cod sursa (job #510682) | Cod sursa (job #1616234) | Cod sursa (job #2052182) | Cod sursa (job #1348583) | Cod sursa (job #2701904)
#include <bits/stdc++.h>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
const int dim1=1e6+5;
const int dim2=2e6+5;
int n;
char t[dim2], v[dim1];
int l[dim2];
void extraprep()
{
int len=strlen(v);
for (int i=len;i>=1;i--)
v[i]=v[i-1];
}
void prep()
{
f>>v;
extraprep();
int len=strlen(v+1);
for (int i=1;i<=len;i++){
t[2*i-1]='#';
t[2*i]=v[i];
}
t[2*len+1]='#';
n=2*len+1;
}
long long manach()
{
long long rez=0;
int r=0,c=0;
for (int i=1;i<=n;i++){
if (r<i)
{
c=i;
r=i;
}
else
l[i]=min(l[2*c-i],r-i);
while (i+l[i]+1<=n && i-l[i]-1>=1 && t[i+l[i]+1]==t[i-l[i]-1])
++l[i];
if (i+l[i]>r)
{
c=i;
r=i+l[i];
}
rez+=(l[i]+1)/2;
}
return rez;
}
int main()
{
prep();
g<<manach();
return 0;
}