Cod sursa(job #2586560)

Utilizator MocalinnoMoca Andrei Catalin Mocalinno Data 21 martie 2020 10:14:00
Problema PScPld Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
const int N(2e6);
string sir, s;
int v[N + 5], n, c, r;
int64_t res;
int main()
{
    fin >> sir;
    s += '#';
    for (const char& ch: sir)
        s += ch, s += '#';
    v[0] = 1;
    n = static_cast<int>(s.size());
    for (int i = 1; i < n; ++i)
    {
        int lg(0);
        if (i <= r)
            lg = min(v[2 * c - i], r - i + 1);
        while (i - lg >= 0 && i + lg < n && s[i - lg] == s[i + lg])
            ++lg;
        v[i] = lg;
        if (i % 2 == 0)
            res += lg / 2;
        else res += (lg + 1) / 2;
    }
    fout << res;
    fin.close();
    fout.close();
    return 0;
}