Pagini recente » Cod sursa (job #3174986) | Cod sursa (job #1085749) | Cod sursa (job #9099) | Cod sursa (job #364780) | Cod sursa (job #2275711)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
const int MAX = 2e6 + 3;
char s[MAX], a[MAX];
int v[MAX], n;
int main()
{
ifstream fcin("pscpld.in");
ofstream fcout("pscpld.out");
fcin>>s;
n = strlen(s);
for(int i=0; i<n; i++)
a[(i+1)*2 ] = s[i];
n = 2*n +3;
a[0]=a[n-1]= '$';
for(int i=1; i<=n-2; i=i+2)
a[i] = '#';
int imax=1, lim=1;
v[1] = 1;
for(int i=2; i<n-1; i++)
{
if(i==lim+1)
{
imax = i;
while(a[i- v[i] ] == a[i+ v[i] ])
++v[i];
lim = i + v[i] - 1;
}
else
{
if( i + v[2*imax-i] - 1 < lim )
{
v[i] = v[2*imax - i];
}
else {
imax = i;
v[i] = lim - i + 1;
while(a[i- v[i] ] == a[i+ v[i] ])
++v[i];
lim = i + v[i] - 1;
}
}
}
long long s = 0;
for(int i=1; i<=n-1; i++)
s = s + v[i] / 2;
fcout << s;
return 0;
}