Prefiksna funkcija

#include <bits/stdc++.h>
using namespace std;
// prefiksna funkcija
vector<int> seq;
vector<int> lps;
vector<int> lastj;

int kmp(int x)
{
    if(seq.size()==0)
    {
        seq.push_back(x);
        lps.push_back(0);
        lastj.push_back(0);
        return 0;
    }
    int j = lastj[lastj.size()-1];
    seq.push_back(x);
    lps.push_back(0);
    int i = seq.size()-1;

    while(seq[i] != seq[j] && j != 0)
    {
        j = lps[j-1];
    }
    if(seq[i] == seq[j])
    {
        lps[i] = j+1;
        lastj.push_back(j+1);
    }
    else
    {
        lps[i] = 0;
        lastj.push_back(0);
    }
    return lps[i];
}


int main() {
    ios::sync_with_stdio(false);
    lastj.push_back(0);
    stringstream res;
    int q;
    cin >> q;

    while(q--)
    {
        char o;
        int x;
        cin >> o;
        if(o == '+')
        {
            cin >> x;
            res << kmp(x) << endl;
        }
        else
        {
            seq.pop_back();
            lps.pop_back();
            lastj.pop_back();
            if(seq.size()==0)
                res << "0" << endl;
            else
                res << lps[lps.size()-1] << endl;
        }
    }
    cout << res.str();
    return 0;
}