Cod sursa(job #2535499)

Utilizator AlexandruGabrielAliciuc Alexandru AlexandruGabriel Data 31 ianuarie 2020 22:09:44
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <bits/stdc++.h>
#define N 1000005

using namespace std;

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

int P[2 * N], n;
char sir[N], s[2 * N];
int ans;

void Manacher()
{
    int C = 0, R = 0;

    for (int i = 1; i <= 2 * n + 1; i++)
    {
        int mirr = 2 * C - i;

        if (i < R)
            P[i] = min(P[mirr], R - i);

        while (s[i + P[i] + 1] == s[i - P[i] - 1])
            P[i]++;

        if (i + P[i] >= R)
        {
            C = i;
            R = i + P[i] - 1;
        }
    }

    for (int i = 1; i <= 2 * n + 1; i++)
        if (P[i] & 1)
            ans += (P[i] / 2 + 1);
        else
            ans += (P[i] / 2);

    fout << ans;
}

int main()
{
    fin >> (sir + 1);
    n = strlen(sir + 1);

    s[0] = '$';
    for (int i = 1; i <= 2 * n + 1; i++)
    {
        if (i & 1)
            s[i] = '#';
        else
            s[i] = sir[i / 2];
    }
    s[2 * n + 2] = '@';

    Manacher();
    return 0;
}