Cod sursa(job #2466892)

Utilizator theo2003Theodor Negrescu theo2003 Data 3 octombrie 2019 10:24:27
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
int main() {
    string s;
    cin>>s;
    long long int total = 0;
    vector<int> e(s.size(), 0), o(s.size(), 0);
    for(int i = 0, l = -1, r = -1; i < s.size(); i++) {
        int ex = 1;
        if(i <= r) {
            ex = min(r - i + 1, o[l + r - i]);
        }
        while((s[i - ex] == s[i + ex]) && ((i + ex) < s.size()) && ((i - ex) >= 0)) {
            ex++;
        }
        o[i] = ex--;
        if((i + ex) > r) {
            l = i - r;
            r = i + ex;
        }
    }
    for(int i = 0, l = -1, r = -1; i < s.size(); i++) {
        int ex = 0;
        if(i <= r) {
            ex = min(r - i + 1, e[l + r - i + 1]);
        }
        while((s[i - ex - 1] == s[i + ex]) && ((i + ex) < s.size()) && ((i - ex - 1) >= 0)) {
            ex++;
        }
        e[i] = ex--;
        if((i + ex) > r) {
            l = i - r - 1;
            r = i + ex;
        }
    }
    for(int x = 0;x<s.size();x++){
        total += e[x];
        total += o[x];
    }
    cout<<total<<'\n';
    return 0;
}