Pagini recente » Cod sursa (job #2835896) | Cod sursa (job #439610) | Cod sursa (job #243000) | Cod sursa (job #1758726) | Cod sursa (job #338914)
Cod sursa(job #338914)
#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;
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++)
{
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]]-1<x+lung-1)
{
lung=poz+v[t[i]]-x;
}
l-=(lung-1);
r+=(lung-1);
}
while(s[l-1]==s[r+1] && l>1 && r<n)
{
op++;
l--;
r++;
lung++;
t[r*2]=t[r*2-1]=i;
}
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]]-1<x+lung-1)
{
lung=poz+v[t[i]]-x;
}
l-=lung;
r+=lung;
}
while(s[l-1]==s[r+1] && l>1 && r<n)
{
op++;
l--;
r++;
lung++;
t[r*2]=t[r*2-1]=i;
}
sol+=lung;
v[i]=lung;
}
if(op>2*n) return 0;
}
printf("%d\n", op);
printf("%d\n", sol);
return 0;
}