#include <iostream>
#include <string>
#include <map>
class KnuthMorrisPatt {
public:
std::string text;
std::string pattern;
int n;
int m;
std::map<int, int> pi;
KnuthMorrisPatt(std::string text_, std::string pattern_) :
text(text_), pattern(pattern_), n(text_.size()), m(pattern_.size()){
compute_prefix_function();
};
void compute_prefix_function() {
pi[1] = 0;
int k = 0;
for(int q = 2; q <= m; q++) {
while(k > 0 && pattern.at(k) != pattern.at(q - 1)) {
k = pi[k];
}
if (pattern.at(k) == pattern.at(q - 1)) k++;
pi[q] = k;
}
};
void match() {
int q = 0;
for(int i = 1; i <= n; i++) {
while(q > 0 && pattern.at(q) != text.at(i - 1)) {
q = pi[q];
}
if (pattern.at(q) == text.at(i - 1)) q++;
if (q == m) {
std::cout << "Pattern occurs with shift " << i - m << std::endl;
q = pi[q];
}
}
};
};
int main(int argc, char *argv[]) {
KnuthMorrisPatt kmp("abcaaababc", "abc");
kmp.match();
}
/Users/syou6162/cpp% ./a.out
Pattern occurs with shift 0
Pattern occurs with shift 7