読者です 読者をやめる 読者になる 読者になる

Knuth-Morris-Pratt algorithm with C++

C++ アルゴリズム
#include <iostream>
#include <string>
#include <map>

// ref http://infoshako.sk.tsukuba.ac.jp/~yamamoto/Courses/files/page2_13.pdf
class KnuthMorrisPatt {
public:
  std::string text;
  std::string pattern;
  int n;
  int m;
  std::map<int, int> pi; // prefix function
  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