Tamflexの貯蔵庫

やる気のない備忘録

C++でのBM法の実装

文字列検索のアルゴリズムの中で比較的高速なものとして有名なBM法
文字列検索を行った時に役に立ったので書いたソースを載せる

なお以下の文献を参考にさせていただきました.
http://www.comp.cs.gunma-u.ac.jp/~koichi/ALG2/9beamerBM.pdf

#include <bits/stdc++.h>

using namespace std;

/*
引数
string s : 文字列
string t : パターン
返り値
int : 左から探索して初めて登場する箇所(見つからなかった場合は-1)
*/
int bm(string s, string t)
{
  int n = s.size();
  int m = t.size();
  map<char,int> f;
  for(int i=0; i<m; i++) f[t[i]] = m-1-i;
  int p = m-1;
  while(p<n)
  {
    int k = m-1;
    while(k >= 0 && t[k] == s[p]) {k--; p--;}
    if(k == -1) return p+1;
    else
    {
      if(f.find(s[p])==f.end()) p += m;
      else p += max(f[s[p]],m-k);
    }
  }
  return -1;
}

int main()
{
  string s, t; cin >> s;
  while(cin >> t) cout << bm(s,t) << endl;
  return 0;
}
  • sample input
aabbccddaa
aab
bccd
aadd
ad
da
  • sample output
0
3
-1
-1
7