Knuth-Morris-Pratt algorithm

例の如く論文執筆に疲れたので，コーディングで息抜きをします．
今回実装したのは，文字列照合アルゴリズムのクヌース-モリス-プラット法（KMP法)です．
アルゴリズムの詳細は，Wikipediaへどうぞ(　ﾟдﾟ　)
http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

実装部

#include <iostream>
#include <vector>

namespace {
void InitTable(const std::string& query,
               std::vector<int>* query_backward_table) {
  std::vector<int>(0).swap(*query_backward_table);
  size_t suffix = 0;
  int prefix = -1;
  for (;
       suffix < query.size();
       ++suffix, ++prefix) {
    query_backward_table->push_back(prefix);
    while ((prefix >= 0) && (query[prefix] != query[suffix]))
      prefix = query_backward_table->at(prefix);
  }
  query_backward_table->push_back(prefix);
}

void KMPSearch(const std::string& text,
               const std::string& query) {
  std::vector<int> query_backward_table;
  InitTable(query, &query_backward_table);

  size_t text_pos = 0;
  int query_pos = 0;
  while (text_pos < text.size()) {
    while (query_pos >= 0 &&
           text[text_pos] != query[query_pos])
      query_pos = query_backward_table[query_pos];
    ++text_pos;
    ++query_pos;

    if (query_pos == (int)query.size()) {
      std::cout << text_pos - query_pos << std::endl;
      query_pos = query_backward_table[query_pos];
    }
  }
}

} //namespace


int main (int argc, char** argv) {
  if (argc != 3) {
    std::cerr << "usage :  ./a.out [text] [query]" << std::endl;
    return -1;
  }

  KMPSearch(argv[1], argv[2]);
  return 0;
}

結果

% ./a.out ababababababababab abab
0
2
4
6
8
10
12
14

% ./a.out abracadabra abra
0
7

% ./a.out マルクス家はユダヤ系であった。けれどもトリエル市のすぐれた弁護士であったハインリッヒ・マルクス一家の生活はかなりゆとりの有るものであった。父マルクスは十八世紀フランス哲学を深く学び、ディド ロー（一七一三―一七八四）や、ヴォルテール（一六九四―一七七八）、悲劇作者ラシーヌの作品などから影響をうけていた。 マルクス
0
129
210

http://www.aozora.gr.jp/cards/000311/files/3265_10920.html より．