Cod sursa(job #2437646)

Utilizator Alex_BubBuburuzan Alexandru Alex_Bub Data 9 iulie 2019 22:13:19
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>
#include <cstring>

using namespace std;

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

const int NMax = 1e6;

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

int Expand(int l, int r)
{
    int Ans = 0;

    while(l <= N && r && A[l] == A[r])
        Ans++, l++, r++;
    return Ans;
}

int main()
{
    fin.getline(A + 1, NMax + 5);
    N = strlen(A + 1);

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

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

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

    for(int i = 1; i <= N; i++)
        DP[i] = 0;

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

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

        DP[i] += Expand(i - DP[i] - 1, i + DP[i] + 2);
        Sol += DP[i] + 1;

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

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

    return 0;
}