A simple C++ implementation of Morris-Pratt search algorithm

morris-pratt.cpp

#include <vector>
#include <iostream>
using namespace std;

void prepare(const vector<int>& x, int m, vector<int>& mpnext) {
    int i = 0;
    int j = -1;
    mpnext[0] = -1;
    while (i < m) {
        while (j>-1 and x[i] != x[j]) j = mpnext[j];
        ++i; ++j;
        mpnext[i] = j;
    }
}

void search(const vector<int>& x, const vector<int>& text) {
    vector<int> pos(text.size());
    prepare(x, x.size(), pos);
    int i = 0;
    int j = 0;
    while (j < text.size()) {
        while (i > -1 and x[i] != text[j]) i = pos[i];
        ++i;
        ++j;
        if (i >= x.size()) {
            cout << "Found: " << j-i << endl;
            i = pos[i];
        }
    }
}

int main() {
    int s1, s2;
    cin >> s1 >> s2;
    vector<int> num(s1);
    vector<int> text(s2);
    cout << "Type the numbers to search" << endl;
    for (int i=0; i<s1; ++i) cin >> num[i];
    cout << "Type the text to search" << endl;
    for (int j=0; j<s2; ++j) cin >> text[j];
    search(num, text);
}