Cod sursa(job #2590570)

Utilizator MatteoalexandruMatteo Verzotti Matteoalexandru Data 28 martie 2020 13:49:29
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 kb
/*
                `-/oo+/-   ``
              .oyhhhhhhyo.`od
             +hhhhyyoooos. h/
            +hhyso++oosy- /s
           .yoooossyyo:``-y`
            ..----.` ``.-/+:.`
                   `````..-::/.
                  `..```.-::///`
                 `-.....--::::/:
                `.......--::////:
               `...`....---:::://:
             `......``..--:::::///:`
            `---.......--:::::////+/`
            ----------::::::/::///++:
            ----:---:::::///////////:`
            .----::::::////////////:-`
            `----::::::::::/::::::::-
             `.-----:::::::::::::::-
               ...----:::::::::/:-`
                 `.---::/+osss+:`
                   ``.:://///-.
*/
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cmath>

using namespace std;
typedef long long i64;

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

const int INF = 2e9;
const int N = 1000000;

string s, aux;
int p[5 + 2 * N];
int n;

i64 Manacher(){
    int l, r;
    i64 ans(0);

    l = 0;
    r = -1;
    for(int i = 0; i < n; i++){
        int k;
        if(i > r) k = 1;
        else k = min(p[l + r - i], r - i + 1);

        while(i - k >= 0 && i + k < n && s[i - k] == s[i + k])
            k++;

        p[i] = k--;

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

        ans += p[i] / 2;
    }

    return ans;
}

int main() {
    in >> aux;
    int sz = aux.size();

    s = '#';
    for(int i = 0; i < sz; i++){
        s += aux[i];
        s += '#';
    }

    n = s.size();
    out << Manacher() << '\n';
    return 0;
}