Cod sursa(job #2926526)

Utilizator LucaMuresanMuresan Luca Valentin LucaMuresan Data 17 octombrie 2022 21:58:19
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <bits/stdc++.h>

using namespace std;

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

string pp (string s)
{
    string q = "^";
    for (int i=0; i<s.size(); i++)
    {
        q += '#';
        q += s[i];
    }
    q += "#$";
    return q;
}

int n;
int l[2000001];

long long manacher(string s)
{
    string q = pp(s);
    n = q.size();

    int c=0, r=0;
    for (int i=1; i+1<n; i++)
    {
        int mirr = c+c-i;

        l[i] = (r > i) ? min(l[mirr], r-i) : 0;

        while (q[i+1 + l[i]] == q[i-1 - l[i]])
            l[i]++;

        if (i + l[i] > r)
        {
            c = i;
            r = i + l[i];
        }
    }

    long long ans = 0;

    /**
    l = 2*k-1 => 2*1-1, 2*2-1, ..., 2*k-1 => k
    l = 2*k => 2*1, 2*2, ..., 2*k => k
    */

    for (int i=1; i+1<n; i++)
        l[i] = (l[i] + 1) / 2, ans += l[i];

    return ans;
}

int main()
{
    string s;
    in >> s;

    out << manacher(s);

    return 0;
}