Cod sursa(job #2810143)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 28 noiembrie 2021 17:15:37
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <bits/stdc++.h>

using namespace std;

inline void Open(const string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}

char s[1000001];

int d1[1000001], d2[1000001];
int n;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    Open("pscpld");

    cin >> s;
    n = strlen(s);

    for(int i = 0, l = 0, r = -1;i < n;i++) {
        int k = (i > r)? 1 : min(d1[l + r - i], r - i + 1);
        while(0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
            k++;
        }

        d1[i] = k--;
        if(i + k > r) {
            l = i - k;
            r = i + k;
        }
    }

    for(int i = 0, l = 0, r = -1;i < n;i++) {
        int k = (i > r)? 0 : min(d2[l + r - i + 1], r - i + 1);
        while(0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) {
            k++;
        }

        d2[i] = k--;
        if(i + k > r) {
            l = i - k - 1;
            r = i + k;
        }
    }

    int ans = 0;
    for(int i = 0;i < n;i++)
        ans += d1[i] + d2[i];

    cout << ans;

    return 0;
}