Cod sursa(job #2798506)

Utilizator Iulia14iulia slanina Iulia14 Data 11 noiembrie 2021 13:43:15
Problema PScPld Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <bits/stdc++.h>

using namespace std;
#define ll long long
const int N = 1e6 + 5;
char s[N];
ll d1[N], d2[N];
int main()
{
    freopen("pscpld.in", "r", stdin);
    freopen("pscpld.out", "w", stdout);
    ll n, l = 1, r = 0, ans = 0;
    cin >> s + 1;
    n = strlen(s + 1);
    for (int i = 1; i <= n; i++)
    {
        ll lg = 1;
        if (i < r)
            lg = min(d1[l + r - i], r - i + 1);
        while (i + lg <= n && lg < i && s[i - lg] == s[i + lg])
            lg++;
        ans += lg;
        d1[i] = lg--;
        if (r < i + lg)
            l = i - lg, r = i + lg;
    }
    l = 1, r = 0;
    for (int i = 1; i <= n; i++)
    {
        ll lg = 0;
        if (i < r)
            lg = min(d2[l + r - i + 1], r - i + 1);
        while (i + lg <= n && lg + 1 < i && s[i - lg - 1] == s[i + lg])
            lg++;
        ans += lg;
        d2[i] = lg--;
        if (r < i + lg && lg)
            l = i - lg - 1, r = i + lg;
    }
    cout << ans;
    return 0;
}