Pagini recente » Cod sursa (job #377583) | Cod sursa (job #520567) | Cod sursa (job #1996738) | Cod sursa (job #2060930) | Cod sursa (job #1738279)
#include <iostream>
#include <cstring>
#include <fstream>
using namespace std;
#define NMAX 1000001*2+2
#define MMAX 1000001
ifstream in("pscpld.in");
ofstream out("pscpld.out");
char a[NMAX],v[MMAX];
long long n,c,p[NMAX],m,d,r;
int main()
{
in >> v;
n = strlen(v);
a[0] = '&';
for(int i=0,k=1;i<n;i++)
{
a[k++]='#';
a[k++] = v[i];
}
a[2*n+1]='#',a[2*n+2]='@';
n=2*n+1;
p[2] = 1;
c = 2;
m = 0;
r=2;
for(int i=3;i<n;i++)
{
m = 2*c-i;
if(i<r) p[i] = min(r-i,p[m]);
else p[i] = 0; //deja 0?
while(a[i+p[i]+1] == a[i-p[i]-1])
{
p[i]++;
}
if(i+p[i]>r)
{
c = i;
r = i+p[i];
}
}
long long cnt = 0;
for(int i=0;i<=n;i++)
{
// cout << p[i] << " ";
if(p[i]%2==0)
cnt += p[i]/2;
else
{
cnt +=p[i]/2+1;
}
}
out <<cnt;
return 0;
}