Cod sursa(job #2409499)

Utilizator akaprosAna Kapros akapros Data 19 aprilie 2019 09:49:31
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <bits/stdc++.h>
#define maxN 1000002

using namespace std;

FILE *fin = freopen("pscpld.in", "r", stdin);
FILE *fout = freopen("pscpld.out", "w", stdout);

char a[maxN], s[2 * maxN];

int p[maxN * 2];

long long ans;

void Manacher(int n)
{
    int N = 2 * n + 1, r = 0, c = 0;
    for (int i = 1; i < N; ++ i)
    {
        int ii = 2 * c - i;
        if (r > i)
            p[i] = min(r - i, p[ii]);
        /// r = i + p[i], pos = 2 * i - i - p[i] - 1 (2 * i - r - 1)
        while (s[i - p[i] - 1] == s[i + p[i] + 1])
            ++ p[i];
        if (i + p[i] > r)
        {
            c = i;
            r = i + p[i];
        }

        ans += (p[i] + 1) / 2;
        // ans = max(ans, p[i]);
    }
}
int main()
{
    scanf("%s\n", a);
    int n = strlen(a);
    s[2 * n + 1] = '*';
    for (int i = 0; i < n; ++ i)
    {
        s[i * 2] = '#';
        s[i * 2 + 1] = a[i];
    }
    s[2 * n] = '#';
    Manacher(n);
    printf("%lld\n", ans);
    return 0;
}