Cod sursa(job #790638)

Utilizator visanrVisan Radu visanr Data 21 septembrie 2012 23:15:46
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;

#define nmax 2000010

char B[nmax], A[nmax];
int lg[nmax];
long long ans = 1;
int N, L, R, C = 1, now;

int main()
{
    ifstream in("pscpld.in");
    ofstream out("pscpld.out");
    int i;
    in >> B;
    now = strlen(B);
    for(i = 0; i < now; i++)
    {
        A[++N] = B[i];
        if(i < now - 1) A[++N] = '#';
    }
    lg[1] = 1;
    for(i = 2; i <= N; i++)
    {
        lg[i] = max(min(lg[2 * C - i] - 1, C + lg[C] - i), 1);
        L = i - lg[i];
        R = i + lg[i];
        while(L > 0 && R <= N && A[L] == A[R])
        {
            L --;
            R ++;
            lg[i] ++;
        }
        if(A[i] == '#') ans += lg[i] / 2;
        else ans += (lg[i] + 1) / 2;
        if(i + lg[i] > C + lg[C]) C = i;
    }
    out << ans;
    return 0;
}