Pagini recente » Cod sursa (job #1934577) | Cod sursa (job #2218333) | Cod sursa (job #2358525) | Cod sursa (job #1725663) | Cod sursa (job #338919)
Cod sursa(job #338919)
#include <stdio.h>
#include <string.h>
using namespace std;
#define maxn 2000010
long n, i, j, k, l, r, lung, poz, sol, x, v[maxn], t[maxn], op, l1, o2;
char s[maxn];
int main()
{
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
gets(s+1);
for(n=1; s[n]>0; ++n);
--n;
for(i=1; i<=2*n-1; i++)
{
// printf("%d: ", i);
if(i&1)
{
x=i/2+1;
l = r = x;
lung=1;
if(t[i])
{
lung=v[2*t[i]-i];
poz=t[i]/2+1;
if(poz+v[t[i]]<x+lung)
{
lung=poz+v[t[i]]-x;
}
l-=(lung-1);
r+=(lung-1);
}
l1=lung;
while(s[l-1]==s[r+1] && l>1 && r<n)
{
op++;
l--;
r++;
lung++;
if(v[t[r*2]]<lung)
{
t[r*2]=t[r*2-1]=i;
}
if(l==1 || r==n) break;
}
sol+=lung;
v[i]=lung;
}
else
{
x=i/2+1;
l=x;
r=l-1;
lung=0;
if(t[i])
{
lung=v[2*t[i]-i];
poz=t[i]/2+1;
if(poz+v[t[i]]<x+lung)
{
lung=poz+v[t[i]]-x;
}
l-=lung;
r+=lung;
}
l1=lung;
while(s[l-1]==s[r+1])
{
op++;
l--;
r++;
lung++;
if(v[t[r*2]]<lung)
{
t[r*2]=t[r*2-1]=i;
}
if(l==1 || r==n) break;
}
sol+=lung;
v[i]=lung;
}
// printf("%d\n", lung-l1);
o2+=lung-l1;
if(op>4*n) return 0;
}
// printf("%d %d %d\n", op, o2, n);
printf("%d\n", sol);
return 0;
}