Pagini recente » Cod sursa (job #938051) | Cod sursa (job #3204444) | Cod sursa (job #1323770) | Cod sursa (job #616879) | Cod sursa (job #1883733)
#include <iostream>
#include <cstdio>
#define NMAX 1000001
using namespace std;
char A[2 * NMAX + 1];
int LPS[2 * NMAX + 1], C, R, N, lmax, cmax, nr;
void read()
{
freopen("pscpld.in", "r", stdin);
A[N++] = '#';
int c;
while(!feof(stdin))
{
scanf("%c", &c);
if(isalpha(c))
{
A[N++] = c;
A[N++] = '#';
}
}
}
void solve()
{
LPS[0] = 0;
LPS[1] = 1;
C = 1;
R = 2;
lmax = cmax = 1;
for(int i = 2; i < N; i++)
{
int ii = 2*C-i;
if(R<i)
LPS[i] = 0;
else
LPS[i] = min(R - i, LPS[ii]);
//Start expand
while(i - LPS[i] > 0 && i + LPS[i] < N)
{
if((i - LPS[i] - 1) % 2 == 0)
LPS[i]++;
else if(A[i - LPS[i] - 1] == A[i + LPS[i] + 1])
LPS[i]++;
else
break;
}
//Stop expand
if(lmax < LPS[i])
{
lmax = LPS[i];
cmax = i;
}
if(i + LPS[i] > R)
{
R = i + LPS[i];
C = i;
}
}
nr = N / 2;
for(int i = 0; i < N; i++)
if(LPS[i] > 1)
nr++;
}
void print()
{
freopen("pscpld.out", "w", stdout);
printf("%d", nr);
}
int main()
{
read();
solve();
print();
return 0;
}