Cod sursa(job #2354299)

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

using namespace std;

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

int l, r, len, d[2000005], N;
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 = 1;
            while (s[i - len] == s[i + len])
            {
                len++;
                if (i - len < 0 || i + len == N)
                    break;
            }
            len--;
            d[i] = len;
            r = i + len;
            l = i - len;
        }
        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 += d[i] / 2 + 1 - i % 2;
    fout << k;
    return 0;
}