Cod sursa(job #2437617)

Utilizator Alex_BubBuburuzan Alexandru Alex_Bub Data 9 iulie 2019 21:05:56
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>

using namespace std;

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

const int NMax = 1e6;

int DP[NMax + 5], C, R, A[NMax + 5], N;
char S[NMax + 5]; long long Sol;

int Expandi(int c, int r)
{
    while(c + r + 1 <= N && c - r - 1 && A[c + r + 1] == A[c - r - 1])
        r++;
    return r;
}

int Expandp(int c, int r)
{
    while(c + r + 2 <= N && c - r - 1 && A[c + r + 2] == A[c - r - 1])
        r++;
    return r;
}

int main()
{
    fin >> S;

    for(int i = 0; S[i]; i++)
        A[++N] = S[i] - 'a';

    for(int i = 1; i <= N; i++)
    {
        if(i <= C + R) DP[i] = DP[C - i];

        DP[i] = Expandi(i, DP[i]);
        Sol += DP[i] + 1;

        if(i + DP[i] > C + R)
            C = i, R = DP[i];
    }
    C = R = 0;

    for(int i = 1; i < N; i++)
    {
        DP[i] = 0;
        if(A[i] != A[i + 1]) continue;

        if(i <= C + R) DP[i] = DP[C - i + 1];

        DP[i] = Expandp(i, DP[i]);
        Sol += DP[i] + 1;

        if(i + DP[i] > C + R)
            C = i, R = DP[i];
    }
    fout << Sol << '\n';

    fin.close();
    fout.close();

    return 0;
}