Pagini recente » Cod sursa (job #1816497) | Cod sursa (job #891896) | Cod sursa (job #2299592) | Cod sursa (job #82245) | Cod sursa (job #790315)
Cod sursa(job #790315)
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define min(a,b) ( (a<b) ? (a) : (b) )
#define maxn 1000005
long Rez[2*maxn];
char Text[2*maxn];
long n,i,last;
long long Rezultat;
int main()
{
freopen ("pscpld.in","r",stdin);
freopen ("pscpld.out","w",stdout);
scanf ("%s", &Text );
n=strlen( Text );
for ( i= (n)*2; i>=0; i-- )
if ( i&1 )
Text[i]=Text[ (i>>1) ];
else
Text[i]='%';
n<<=1;
for ( i=0; i<=n; i++ )
{
if ( Rez[last]+last >= i )
Rez[i]=min ( Rez[ 2*last-i ] , last+Rez[last]-i );
while ( ( i-Rez[i]-1 >= 0 )
&& ( i+Rez[i]+1<=n )
&& ( Text [ i+Rez[i]+1 ] == Text [ i-Rez[i]-1 ] ) )
Rez[i]++;
Rezultat+= ( Rez[i]+(i&1) )>>1;
}
printf("%lld\n", Rezultat );
return 0;
}