Cod sursa(job #2305745)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 20 decembrie 2018 23:10:40
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>

using namespace std;

int main() {

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

    string s;
    in >> s;

    vector<char> v(s.size() * 2 + 1);
    int ii = 0;
    v[ii ++] = '$';
    for(auto it : s) {
        v[ii ++] = it;
        v[ii ++] = '$';
    }


    vector<int> p(v.size(), 0);
    int r = 0, pos = 0;
    int ans = 0;

    for(int i = 1; i < v.size(); i ++) {

        if(r > i)
            p[i] = min(r - i + 1, p[2 * pos - i]);

        while(i - p[i] - 1 >= 0 && v[i + p[i] + 1] == v[i - p[i] - 1])
            p[i] ++;


        if(i + p[i] > r) {
            r = i + p[i];
            pos = i;
        }

        ans += ((p[i] + 1) / 2);

    }
    out << ans;

    return 0;
}