Skip to content

Instantly share code, notes, and snippets.

@appplemac
Created May 31, 2013 16:20
Show Gist options
  • Save appplemac/5686106 to your computer and use it in GitHub Desktop.
Save appplemac/5686106 to your computer and use it in GitHub Desktop.
A simple C++ implementation of Morris-Pratt search algorithm
#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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment