Cod sursa(job #2305729)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 20 decembrie 2018 22:22:45
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 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;
    p[0] = 1;
    int ans = 0;

    for(int i = 1; i < v.size(); i ++) {
        if(i > r)
            p[i] = 1;
        else {
            int dif = i - pos;
            p[i] = min(r - i + 1, p[pos - dif]);
        }

        int j = i - p[i], k = i + p[i];
        while(j >= 0 && k < v.size() && v[j] == v[k]) {
            j --;
            k ++;
            p[i] ++;
        }

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

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

       //cout << v[i] << " " << i << " " << p[i] << endl;
    }
    out << ans;


    return 0;
}