Pagini recente » Cod sursa (job #894034) | Cod sursa (job #1829339) | Cod sursa (job #359390) | Cod sursa (job #1503072) | Cod sursa (job #2068806)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int nr[1000000];
int main()
{
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
char a[2000001];
int L[100000], n;
cin.getline(a, 1000000);
n=strlen(a);
n=n*2+1;
int c=2;
int r=3;
L[0]=0;
L[1]=1;
for(int i=2; i<n; i++)
{
int oglindit=c*2-i;
L[i]=0;
int dif=r-i;
if(dif>0)
L[i]=min(L[oglindit], dif);
while ( ((i + L[i]) < n && (i - L[i]) > 0) && ( ((i + L[i] + 1) % 2 == 0) || (a[(i + L[i] + 1)/2] == a[(i - L[i] - 1)/2] )))
L[i]++;
if(i+L[i]>r)
{
c=i;
r=i+L[i];
}
}
int k=2;
while(k<n)
{
for(int i=0; i<n; i++)
if(L[i]==k)
nr[k]++;
k++;
}
int counter=0;
for(int i=0; i<n; i++)
if(nr[i]>0)
counter+=nr[i];
printf("%d", counter+(n-1)/2);
return 0;
}