Cod sursa(job #2068860)

Utilizator dragomirmanuelDragomir Manuel dragomirmanuel Data 18 noiembrie 2017 11:29:13
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

const int NMax = 1000005;
char s[NMax];
int lp[2*NMax-5];

void Manacher()
{
    int C = 1;
    int R = 2;
    int iMirror;
    int N = strlen(s);
    N = 2 * N + 1;
    lp[0] = 0;
    lp[1] = 1;

    for(int i=2; i < N; ++i)
    {
        iMirror = 2 * C - i;
        lp[i] = 0;

        int diff = R - i;

        if(diff > 0)
        {
            lp[i] = min(lp[iMirror], diff);
        }

        while (((i + lp[i]) < N && (i - lp[i]) > 0) &&
                (((i + lp[i] + 1) % 2 == 0) ||
            (s[(i + lp[i] + 1)/2] == s[(i - lp[i] - 1)/2] )))
        {
            lp[i]++;
        }

        if(i + lp[i] > R)
        {
            C = i;
            R = i + lp[i];
        }
    }
}

int main()
{
    ifstream fin("pscpld.in");
    ofstream fout("pscpld.out");

    fin >> s;
    Manacher();

    long long sum = 0;

    int N = strlen(s);
    N = 2*N + 1;
    for(int i=1; i<N; ++i)
    {
        if(lp[i]%2 == 1)
            sum += lp[i]/2 + 1;

        else
            sum += lp[i]/2;
    }

    fout << sum;
    return 0;
}