Pagini recente » Cod sursa (job #2335487) | Cod sursa (job #1466150) | Cod sursa (job #188415) | Cod sursa (job #1397261) | Cod sursa (job #790630)
Cod sursa(job #790630)
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define nmax 2000010
char B[nmax], A[nmax];
int lg[nmax] = {0, 1};
long long ans = 1;
int N, left, right, C = 1, now;
int main()
{
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
int i;
scanf("%s", B);
now = strlen(B);
for(i = 0; i < now; i++)
{
A[++N] = B[i];
if(i < now - 1) A[++N] = '#';
}
for(i = 2; i <= N; i++)
{
lg[i] = min(lg[2 * C - 1] - 1, C + lg[C] - i);
lg[i] = max(lg[i], 1);
left = i - lg[i];
right = i + lg[i];
for(; left > 0 && right <= N && A[left] == A[right]; lg[i] ++, right ++, left --);
if(A[i] == '#') ans += lg[i] / 2;
else ans += (lg[i] + 1) / 2;
if(i + lg[i] > C + lg[C]) C = i;
}
printf("%lld\n", ans);
return 0;
}