Cod sursa(job #3196640)

Utilizator not_anduAndu Scheusan not_andu Data 24 ianuarie 2024 14:14:15
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <bits/stdc++.h>
#pragma GCC optimize ("03")

using namespace std;

#define INFILE "pscpld.in"
#define OUTFILE "pscpld.out"

typedef long long ll;

const int N_MAX = 1e6 + 5;

int palindrom[2 * N_MAX + 1];

void solve(){

    string aux; cin >> aux;
    string s;

    for(auto &ch : aux){
        s += '$';
        s += ch;
    }
    s += '$';

    int left = 0, right = 0;
    for(int i = 0; i < s.size(); ++i){
        
        if(i < right){
            palindrom[i] = min(right - i + 1, palindrom[left + right - i]);
        }
        
        while(i - palindrom[i] >= 0 && i + palindrom[i] < s.size() && s[i - palindrom[i]] == s[i + palindrom[i]]){
            palindrom[i]++;
        }

        if(i + palindrom[i] - 1 > right){
            right = i + palindrom[i] - 1;
            left = i - palindrom[i] + 1;
        }

    }

    ll ans = 0;
    for(int i = 0; i < s.size(); ++i){
        ans += palindrom[i] / 2;
    }

    cout << ans << '\n';

}

int main(){
    ios_base::sync_with_stdio(false);
    freopen(INFILE, "r", stdin);
    freopen(OUTFILE, "w", stdout);
    cin.tie(0), cout.tie(0);
    solve();
    return 0;
}