Cod sursa(job #2354306)

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

using namespace std;

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

long long l, r, len, N;
long long k, d[2000005];
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 (s[i - len] == s[i + len])
            {
                len++;
                if (i - len < 0 || i + len == N)
                    break;
            }
        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;
}