Cod sursa(job #2305696)

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

using namespace std;

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

int main() {

    string s;
    in >> s;

    string v;
    v = v + '$';
    for(auto it : s) {
        v = v + it;
        v = v + '$';
    }

    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(r < i) {
            int j = i - 1, k = i + 1;
            p[i] = 1;
            while(j >= 0 && k < v.size() && v[j] == v[k]) {
                j --;
                k ++;
                p[i] ++;
            }
        } else {
            int dif = i - pos;

            if(p[pos - dif] + i - 1 < r) {
                p[i] = p[pos - dif];
            } else {
                int j = i - p[pos - dif], k = i + p[pos - dif];
                p[i] = p[pos - dif];
                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);
    }
    out << ans;

    return 0;
}