Cod sursa(job #790630)

Utilizator visanrVisan Radu visanr Data 21 septembrie 2012 23:03:48
Problema PScPld Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#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;
}