Skip to content

Instantly share code, notes, and snippets.

@hsinewu
Last active May 17, 2021 11:34
Show Gist options
  • Save hsinewu/44a1ce38a1baf47893922e3f54807713 to your computer and use it in GitHub Desktop.
Save hsinewu/44a1ce38a1baf47893922e3f54807713 to your computer and use it in GitHub Desktop.
Knuth–Morris–Pratt algorithm in c++
#include <iostream>
#include <algorithm>
using namespace std;
int find_substring(string str, string pattern) {
// Step 0. Should not be empty string
if( str.size() == 0 || pattern.size() == 0)
return -1;
// Step 1. Compute failure function
int failure[pattern.size()];
std::fill( failure, failure+pattern.size(), -1);
for(int r=1, l=-1; r<pattern.size(); r++) {
while( l != -1 && pattern[l+1] != pattern[r])
l = failure[l];
// assert( l == -1 || pattern[l+1] == pattern[r]);
if( pattern[l+1] == pattern[r])
failure[r] = ++l;
}
// Step 2. Search pattern
int tail = -1;
for(int i=0; i<str.size(); i++) {
while( tail != -1 && str[i] != pattern[tail+1])
tail = failure[tail];
if( str[i] == pattern[tail+1])
tail++;
if( tail == pattern.size()-1)
return i - tail;
}
return -1;
}
int main() {
cout << find_substring("abcd", "abcd") << endl;
cout << find_substring("abcd", "ab") << endl;
cout << find_substring("ab", "abcd") << endl;
cout << find_substring("ababc", "abc") << endl;
return 0;
}
@SavicStefan
Copy link

Is this algorithm fast?

@hsinewu
Copy link
Author

hsinewu commented Jul 3, 2019

@SavicStefan
The algorithm is good enough for general purpose, with complexity O(n). See also wikipedia.

That said, I didn't test this implementation extensively( I code it on geeksforgeeks and passed), that's all I can say.

Thanks for your attention.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment