文字列検索アルゴリズム一覧

文字列検索の計算量を減らしたいときに使われるアルゴリズムの一覧です。といっても、2019/07/29現在はローリングハッシュのみです。随時追加していきます。【2019/07/30追記】Z AlgorithmとKMP法と接尾辞配列の項目を追加しました。

文字列\(S\)に部分文字列\(T\)が存在するかどうかを判定したいとき、すぐに思いつく方法の計算量は\(O(|S||T|)\)です。この計算量を減らすことが目標です。

ローリングハッシュ

文字列検索アルゴリズムの中では、おそらく最も実装量の少ない方法です。

ハッシュ値の累積和のようなものを前計算しておくことで、部分文字列のハッシュ値を\(O(1)\)で求めることができます（文字を整数として見るとスッと理解できます）。2つのハッシュ値を比較することで、文字列が一致するかどうかを判定できます。文字列が異なっていてハッシュ値が同じになる可能性は非常に低いため、無視していいようです。伝聞の情報で申し訳ないです。

前計算には\(O(|S|+|T|)\)かかります。

実装

hとbは互いに素かつ1 < b < hであれば何でもよいです。

struct RollingHash {
  const int h = 1000000007;
  const int b = 10007;
  vector<int> ha;
  vector<int> po;
  RollingHash(const string &s) {
    int n = (int) s.size();
    ha.assign(n + 1, 0);
    po.assign(n + 1, 1);
    for (int i = 0; i < n; i++) {
      ha[i + 1] = ((long long) ha[i] * b + s[i]) % h;
      po[i + 1] = ((long long) po[i] * b) % h;
    }
  }
  int get(int l, int r) {
    return (ha[r] + h - ((long long) ha[l] * po[r - l]) % h) % h;
  }
};

使用例

String Search | Aizu Online Judge

RollingHash構造体の定義は省略しています。

int main() {
  string T, P;
  cin >> T >> P;
  auto th = RollingHash(T);
  auto ph = RollingHash(P);
  for (int i = 0; i + P.size() <= T.size(); i++) {
    if (th.get(i, i + P.size()) == ph.get(0, P.size())) {
      cout << i << endl;
    }
  }
  return 0;
}

Z Algorithm

\(T\)と\(S\)をこの順番で連結した文字列の最長共通接頭辞数の配列があれば、\(T\)に一致する\(S\)の部分文字列のインデックス一覧が\(O(|S|)\)で得られます。実はZ Algorithmと呼ばれるアルゴリズムを使うことで、計算量\(O(|S| + |T|)\)で最長共通接頭辞数の配列を作れます。Z Algorithmについてはすぬけさんの記事で詳しく解説されています。複雑度高めです。僕自身まだよく理解できていません。

snuke.hatenablog.com

以下がZ Algorithmの実装です。すぬけさんの実装のコピペです。

vector<int> z_algorithm(const string &s) {
  int n = s.size();
  vector<int> a(n);
  a[0] = n;
  int i = 1, j = 0;
  while (i < n) {
    while (i + j < n && s[j] == s[i + j]) j++;
    a[i] = j;
    if (j == 0) { i++; continue; }
    int k = 1;
    while (i + k < n && k + a[k] < j) a[i + k] = a[k], k++;
    i += k, j -= k;
  }
  return a;
}

理解したので追記します。

jは文字列の前のほうを左右にうろうろし、対してiは順序良く右に移動していきます。左に移動するのはjだけ、という前提でコードを読むと理解しやすいです。j = 0のときはそれより左に移動させられないため、iだけ右に進めます。

kについては言葉での説明が難しいので図だけ載せておきます。大文字の\(A\)は最長共通接頭辞数の配列を表します。

使用例

String Search | Aizu Online Judge

z_algorithm()の定義は省略しています。

int main() {
  string t, p;
  cin >> t >> p;
  int n = t.size();
  t = p + t;
  auto zi = z_algorithm(t);
  for (int i = p.size(); i < n + p.size(); i++) {
    if (zi[i] >= p.size()) {
      cout << i - p.size() << endl;
    }
  }
  return 0;
}

KMP法

難しいです。理解できていません。

mayokoex.hatenablog.com

以下の実装は、mayokoさんの実装そのままです。

vector<int> kmp(const string &s, const string &t) {
  vector<int> ta(t.size() + 1);
  {
    ta[0] = -1;
    int j = -1;
    for (int i = 0; i < t.size(); i++) {
      while (j >= 0 && t[i] != t[j]) j = ta[j];
      ta[i + 1] = ++j;
    }
  }
  vector<int> ret;
  int m = 0, i = 0, n = s.size();
  while (m + i < n) {
    if (t[i] == s[m + i]) {
      if (++i == (int) t.size()) {
        ret.push_back(m);
        m = m + i - ta[i];
        i = ta[i];
      }
    } else {
      m = m + i - ta[i];
      if (i > 0) i = ta[i];
    }
  }
  return ret;
}

使用例

String Search | Aizu Online Judge

kmp()の定義は省略しています。

int main() {
  string t, p;
  cin >> t >> p;
  auto r = kmp(t, p);
  for (int i = 0; i < r.size(); i++) {
    cout << r[i] << endl;
  }
  return 0;
}

接尾辞配列

接尾辞配列を作っておけば、文字列検索が\(O(|T| \log |S|)\)で終わります。これは、\(|S|\)が大きい場合にRollingHashと比べて高速です。

問題は構築の計算量ですが、蟻本の方法では\(O(|S| \log ^ 2 |S|)\)です。これは、\(|S| = 10 ^ 6\)のときに\(4 \times 10 ^ 8\)であるため、制約によってはTLEします。

以下が、蟻本の実装を真似た計算量\(O(|S| \log ^ 2 |S|)\)のコードです。

vector<int> suffix_array(const string &s) {
  int n = s.size();
  int k;
  vector<int> sa(n + 1);
  vector<int> rank(n + 1);
  vector<int> tmp(n + 1);
  auto compare = [&](int i, int j) {
    if (rank[i] != rank[j]) return rank[i] < rank[j];
    int ri = i + k <= n ? rank[i + k] : -1;
    int rj = j + k <= n ? rank[j + k] : -1;
    return ri < rj;
  };
  for (int i = 0; i <= n; i++) {
    sa[i] = i;
    rank[i] = i < n ? s[i] : -1;
  }
  for (k = 1; k <= n; k <<= 1) {
    sort(sa.begin(), sa.end(), compare);
    tmp[sa[0]] = 0;
    for (int i = 1; i <= n; i++) {
      tmp[sa[i]] = tmp[sa[i - 1]] + compare(sa[i - 1], sa[i]);
    }
    rank.swap(tmp);
  }
  return sa;
}

実は、接尾辞配列を\(O(|S|)\)で構築するSA-ISというアルゴリズムがあります。以下がSA-ISの実装です（約100行）。string型の文字列を渡すことで接尾辞配列が構築されます。#include <bits/stdc++.h>とusing namespace std;があれば使えます。

struct SuffixArray {
  vector<int> sa;
  SuffixArray(const string &s) {
    sa = sa_is(s);
  }
  int operator[](int k) {
    return sa[k];
  }
  vector<int> sa_is(const string &s) {
    vector<char> c(s.begin(), s.end());
    c.push_back('\0');
    return sa_is(c, 128);
  }
  template <typename T>
  vector<int> sa_is(vector<T> &s, int k) {
    int n = s.size();
    vector<bool> t(n);
    t[n - 1] = 1;
    for (int i = n - 2; i >= 0; i--) {
      t[i] = s[i] < s[i + 1] || s[i] == s[i + 1] && t[i + 1];
    }
    vector<int> lmss;
    for (int i = 0; i < n; i++) {
      if (is_lms(t, i)) lmss.push_back(i);
    }
    vector<int> sa = induced_sort(s, k, t, lmss);
    int n1 = 0;
    for (int i = 0; i < n; i++) {
      if (is_lms(t, sa[i])) sa[n1++] = sa[i];
    }
    for (int i = n1; i < n; i++) {
      sa[i] = -1;
    }
    int name = 0, prev = -1;
    for (int i = 0; i < n1; i++) {
      int pos = sa[i];
      bool diff = false;
      for (int d = 0; d < n; d++) {
        if (prev == -1 || s[pos + d] != s[prev + d] || t[pos + d] != t[prev + d]) {
          diff = true;
          break;
        } else if (d > 0 && (is_lms(t, pos + d) || is_lms(t, prev + d))) {
          break;
        }
      }
      if (diff) name++, prev = pos;
      pos = (pos % 2 == 0) ? pos / 2 : (pos - 1) / 2;
      sa[n1 + pos] = name - 1;
    }
    vector<int> nums;
    for (int i = n1; i < n; i++) {
      if (sa[i] >= 0) nums.push_back(sa[i]);
    }
    if (name < n1) {
      sa = sa_is(nums, name + 1);
    } else {
      for (int i = 0; i < n1; i++) {
        sa[nums[i]] = i;
      }
    }
    vector<int> seed;
    for (int i = 0; i < n1; i++) {
      seed.push_back(lmss[sa[i]]);
    }
    return induced_sort(s, k, t, seed);
  }
  template <typename T>
  vector<int> induced_sort(vector<T> &s, int k, vector<bool> &t, vector<int> &lmss) {
    int n = s.size();
    vector<int> sa(n, -1);
    vector<int> bin(k + 1);
    for (int i = 0; i < n; i++) bin[s[i] + 1]++;
    for (int i = 0; i < k; i++) bin[i + 1] += bin[i];
    vector<int> cnt(k);
    for (int i = lmss.size() - 1; i >= 0; i--) {
      auto c = s[lmss[i]];
      sa[bin[c + 1] - cnt[c] - 1] = lmss[i];
      cnt[c]++;
    }
    cnt.assign(k, 0);
    for (int i = 0; i < n; i++) {
      if (sa[i] <= 0 || t[sa[i] - 1]) continue;
      auto c = s[sa[i] - 1];
      sa[bin[c] + cnt[c]] = sa[i] - 1;
      cnt[c]++;
    }
    cnt.assign(k, 0);
    for (int i = n - 1; i >= 0; i--) {
      if (sa[i] <= 0 || !t[sa[i] - 1]) continue;
      auto c = s[sa[i] - 1];
      sa[bin[c + 1] - cnt[c] - 1] = sa[i] - 1;
      cnt[c]++;
    }
    return sa;
  }
  inline bool is_lms(vector<bool> &t, int i) {
    return i > 0 && t[i] && !t[i - 1];
  }
};

コードの内容について軽く触れておきます。

t配列はS型かどうかの情報を持ちます。よって要素の値が偽のときはL型です。

最初はメモリ節約のために、S型かどうかはビットで管理したほうがいいと思い修正したのですが、メモリ使用量がほぼ変わらなかったのでvector<bool>型に戻しました。

関数ではなく構造体にしている理由は、関数だとsa_isをラムダとして定義するときに困るからです。sa_isは再帰関数なので定義時にfunction<...>を使う必要がありますが、<...>にautoを含めることができないため「色んな型を受け取れる引数」を定義できません。この点を解決できれば関数にすると思います。

以下の記事の実装をベースにしています（ありがとうございます！）。LMS部分文字列をソートする部分だけは論文の実装にしています。これはメモリ節約のためです（メモリ使用量が2/3くらいになります）。

mametter.hatenablog.com

実のところ、ほとんどの部分は理解できていない状態です。なので何かバグがあるかもです。一応こちらの問題とこちらの問題でAcceptは出せていますが…。バグがあればまた修正します。

使用例

String Search | Aizu Online Judge

SuffixArray構造体の定義は省略しています。

int main() {
  string t, p;
  cin >> t >> p;
  auto sa = SuffixArray(t);
  int n = t.size();
  int ll, rr;
  {
    int l = 0, r = n + 1;
    while (r - l > 1) {
      int m = (l + r) / 2;
      if (t.compare(sa[m], p.size(), p) < 0) l = m;
      else r = m;
    }
    ll = r;
  }
  {
    int l = 0, r = n + 1;
    while (r - l > 1) {
      int m = (l + r) / 2;
      if (t.compare(sa[m], p.size(), p) <= 0) l = m;
      else r = m;
    }
    rr = r;
  }
  vector<bool> ans(n);
  for (int i = ll; i < rr; i++) {
    ans[sa[i]] = true;
  }
  for (int i = 0; i < n; i++) {
    if (ans[i]) cout << i << endl;
  }
  return 0;
}

まとめ

文字列検索の際に使われるアルゴリズムは、他のアルゴリズム（ダイクストラ法や累積和など）に比べて複雑度が高いです。理解するのは大変ですが、じっくりと考えて理解していこうと思います。