Cod sursa(job #2354808)

Utilizator niculaandreiNicula Andrei Bogdan niculaandrei Data 25 februarie 2019 16:44:33
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <bits/stdc++.h>

using namespace std;

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

int l, r, len, N, d[2000005];
long long k;
char s[2000005];

int main()
{
    fin.getline(s, 1000001);
    N = strlen(s);
    for (int i = N - 1; i >= 0; i--)
        s[i * 2] = s[i];
    N = 2 * N - 1;
    for (int i = 1; i < N; i += 2)
        s[i] = '#';
    for (int i = 0; i < N; i++)
    {
        if (i > r)
            len = 0;
        else
            len = min(d[l + r - i], r - i);
        while (i - len >= 0 && i + len < N && s[i - len] == s[i + len])
                len++;
        len--;
        d[i] = len;
        if (i + len > r)
        {
            r = i + len;
            l = i - len;
        }
    }
    for (int i = 0; i < N; i++)
        k += 1LL * d[i] / 2 + 1 - i % 2;
    fout << k;
    return 0;
}