Cod sursa(job #1151233)

Utilizator otto1Palaga Vicentiu-Octavian otto1 Data 23 martie 2014 22:41:31
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int NMAX = 2000010;

int M, N, P[NMAX], R, C;
long long Ans;
char S[NMAX], A[NMAX];

int main()
{
    freopen("pscpld.in", "r", stdin);
    freopen("pscpld.out", "w", stdout);

    gets(A + 1); M = strlen(A + 1);
    S[++ N] = '*';
    for(int i = 1; i <= M; ++ i)
        S[++ N] = A[i], S[++ N] = '*';

    for(int i = 1; i <= N; ++ i)
    {
        if(i <= R) P[i] = max(min(P[2 * C - i], R - i), 1);
        while(i - P[i] >= 1 && i + P[i] <= N && S[i - P[i]] == S[i + P[i]]) P[i] ++;
        P[i] --;
        if(i + P[i] > R) C = i, R = i + P[i];
        Ans += (P[i] + 1) / 2;
    }

    printf("%lld\n", Ans);
}