接尾辞配列 (suffix array)
(include/emthrm/string/suffix_array.hpp)

• View this file on GitHub
• Last update: 2023-07-07 02:42:02+09:00
• Include: #include "emthrm/string/suffix_array.hpp"

文字列の全接尾辞を辞書順に並べた配列である。

時間計算量

テキスト長を $N$、パターン長を $M$ とおくと $\langle O(N\log{N}), O(M\log{N}) \rangle$

仕様

template <typename T = std::string>
requires requires { typename T::value_type; }
struct SuffixArray;

• T：$S$ の要素型

メンバ変数

名前	説明
std::vector<int> sa	接尾辞配列
std::vector<int> rank	$\mathrm{rank}_i$ は S[i:] の接尾辞配列中での位置を表す。

メンバ関数

名前	効果・戻り値
explicit SuffixArray(const T& s_, const typename T::value_type sentinel = 0);	$S$ に対してオブジェクトを構築する。
std::vector<int> match(T* t) const;	$T$ が出現する文字列 $S$ 中の位置

参考文献

• https://github.com/beet-aizu/library/blob/2ecdc969043f5276c3782a7752592bd3fe856524/string/suffixarray.cpp
• 秋葉拓哉，岩田陽一，北川宜稔：プログラミングコンテストチャレンジブック [第2版]，pp.335-339，マイナビ出版（2012）
• http://wk1080id.hatenablog.com/entry/2018/12/25/005926

TODO

• パターンマッチングを $O(M + \log{N})$ に高速化する。
  • http://www.prefield.com/algorithm/string/suffix_array.html
• SA-IS
  • https://qiita.com/flare/items/ac11972dbc590a91980d
  • https://topcoder.g.hatena.ne.jp/iwiwi/20110720/1311168147
  • https://mametter.hatenablog.com/entry/20180130/p1
  • https://shogo82148.github.io/homepage/memo/algorithm/suffix-array/sa-is.html
  • http://gasin.hatenadiary.jp/entry/2017/06/08/101525
  • http://sile.hatenablog.jp/entry/20101213/1292190698
  • https://lumakernel.github.io/ecasdqina/string/SA-IS
  • https://github.com/atcoder/ac-library/blob/master/atcoder/string.hpp#L51
  • https://gist.github.com/tjkendev/99d7330fe5642004b68268b31ba38ad4
  • https://docs.google.com/presentation/d/1R9ZgXqX4bpkO3nYkVoqU9Ng2uCIKLbf-UJ2C6hlVYFI
  • https://github.com/defineProgram/JOISS-2020/blob/master/doc/SA-IS.pdf
• 接尾辞オートマトン (suffix automaton)
  • https://ja.wikipedia.org/wiki/%E6%8E%A5%E5%B0%BE%E8%BE%9E%E3%82%AA%E3%83%BC%E3%83%88%E3%83%9E%E3%83%88%E3%83%B3
  • https://w.atwiki.jp/uwicoder/pages/2842.html
  • https://github.com/KodamaD/JOISS2020/blob/master/docs/presentation.pdf
  • https://github.com/spaghetti-source/algorithm/blob/master/string/suffix_automaton.cc
  • https://codeforces.com/contest/1780/problem/G
• 接尾辞木 (suffix tree)
  • https://ja.wikipedia.org/wiki/%E6%8E%A5%E5%B0%BE%E8%BE%9E%E6%9C%A8
  • https://qiita.com/goonew/items/548fe90e9f68c6bba9e9
  • https://docs.google.com/presentation/d/1m-FpwlEg47kHCQx7FSImN0bPY7XJToRVbSMeCsLpI7g
  • https://github.com/spaghetti-source/algorithm/blob/master/string/suffix_tree.cc
  • https://github.com/eandbsoftware/libraryCPP/tree/master/Ukkonen

Submissons

https://onlinejudge.u-aizu.ac.jp/solutions/problem/ALDS1_14_B/review/4972832/emthrm/C++17

Required by

• longest common prefix (include/emthrm/string/longest_common_prefix.hpp)

Verified with

• 文字列/longest common prefix (test/string/longest_common_prefix.test.cpp)
• 文字列/接尾辞配列 (test/string/suffix_array.test.cpp)

Code

#ifndef EMTHRM_STRING_SUFFIX_ARRAY_HPP_
#define EMTHRM_STRING_SUFFIX_ARRAY_HPP_

#include <algorithm>
#include <numeric>
#include <string>
#include <vector>

namespace emthrm {

template <typename T = std::string>
requires requires { typename T::value_type; }
struct SuffixArray {
  std::vector<int> sa, rank;

  explicit SuffixArray(const T& s_, const typename T::value_type sentinel = 0)
      : s(s_) {
    const int n = s.size();
    s.push_back(sentinel);
    sa.resize(n + 1);
    std::iota(sa.rbegin(), sa.rend(), 0);
    std::ranges::stable_sort(
        sa, {}, [this](const int index) -> int { return s[index]; });
    rank.resize(n + 1);
    for (int i = 0; i <= n; ++i) {
      rank[i] = s[i];
    }
    std::vector<int> tmp(n + 1), prev_sa(n + 1);
    for (int len = 1; len <= n; len <<= 1) {
      tmp[sa[0]] = 0;
      for (int i = 1; i <= n; ++i) {
        if (rank[sa[i - 1]] == rank[sa[i]] && sa[i - 1] + len <= n &&
            rank[sa[i - 1] + (len >> 1)] == rank[sa[i] + (len >> 1)]) {
          tmp[sa[i]] = tmp[sa[i - 1]];
        } else {
          tmp[sa[i]] = i;
        }
      }
      rank.swap(tmp);
      std::iota(tmp.begin(), tmp.end(), 0);
      std::copy(sa.begin(), sa.end(), prev_sa.begin());
      for (int i = 0; i <= n; ++i) {
        const int idx = prev_sa[i] - len;
        if (idx >= 0) sa[tmp[rank[idx]]++] = idx;
      }
    }
    for (int i = 0; i <= n; ++i) {
      rank[sa[i]] = i;
    }
  }

  std::vector<int> match(T* t) const {
    const int lb = lower_bound(t);
    ++t->back();
    const int ub = lower_bound(t);
    --t->back();
    std::vector<int> res(ub - lb);
    std::copy(sa.begin() + lb, sa.begin() + ub, res.begin());
    std::sort(res.begin(), res.end());
    return res;
  }

 private:
  T s;

  int lower_bound(const T* t) const {
    const int s_size = s.size(), t_size = t->size();
    int lb = 0, ub = s_size;
    while (ub - lb > 1) {
      const int mid = std::midpoint(lb, ub);
      int s_idx = sa[mid], t_idx = 0;
      bool finished = false;
      for (; s_idx < s_size && t_idx < t_size; ++s_idx, ++t_idx) {
        if (s[s_idx] != (*t)[t_idx]) {
          (s[s_idx] < (*t)[t_idx] ? lb : ub) = mid;
          finished = true;
          break;
        }
      }
      if (!finished) (s_idx == s_size && t_idx < t_size ? lb : ub) = mid;
    }
    return ub;
  }
};

}  // namespace emthrm

#endif  // EMTHRM_STRING_SUFFIX_ARRAY_HPP_

#line 1 "include/emthrm/string/suffix_array.hpp"



#include <algorithm>
#include <numeric>
#include <string>
#include <vector>

namespace emthrm {

template <typename T = std::string>
requires requires { typename T::value_type; }
struct SuffixArray {
  std::vector<int> sa, rank;

  explicit SuffixArray(const T& s_, const typename T::value_type sentinel = 0)
      : s(s_) {
    const int n = s.size();
    s.push_back(sentinel);
    sa.resize(n + 1);
    std::iota(sa.rbegin(), sa.rend(), 0);
    std::ranges::stable_sort(
        sa, {}, [this](const int index) -> int { return s[index]; });
    rank.resize(n + 1);
    for (int i = 0; i <= n; ++i) {
      rank[i] = s[i];
    }
    std::vector<int> tmp(n + 1), prev_sa(n + 1);
    for (int len = 1; len <= n; len <<= 1) {
      tmp[sa[0]] = 0;
      for (int i = 1; i <= n; ++i) {
        if (rank[sa[i - 1]] == rank[sa[i]] && sa[i - 1] + len <= n &&
            rank[sa[i - 1] + (len >> 1)] == rank[sa[i] + (len >> 1)]) {
          tmp[sa[i]] = tmp[sa[i - 1]];
        } else {
          tmp[sa[i]] = i;
        }
      }
      rank.swap(tmp);
      std::iota(tmp.begin(), tmp.end(), 0);
      std::copy(sa.begin(), sa.end(), prev_sa.begin());
      for (int i = 0; i <= n; ++i) {
        const int idx = prev_sa[i] - len;
        if (idx >= 0) sa[tmp[rank[idx]]++] = idx;
      }
    }
    for (int i = 0; i <= n; ++i) {
      rank[sa[i]] = i;
    }
  }

  std::vector<int> match(T* t) const {
    const int lb = lower_bound(t);
    ++t->back();
    const int ub = lower_bound(t);
    --t->back();
    std::vector<int> res(ub - lb);
    std::copy(sa.begin() + lb, sa.begin() + ub, res.begin());
    std::sort(res.begin(), res.end());
    return res;
  }

 private:
  T s;

  int lower_bound(const T* t) const {
    const int s_size = s.size(), t_size = t->size();
    int lb = 0, ub = s_size;
    while (ub - lb > 1) {
      const int mid = std::midpoint(lb, ub);
      int s_idx = sa[mid], t_idx = 0;
      bool finished = false;
      for (; s_idx < s_size && t_idx < t_size; ++s_idx, ++t_idx) {
        if (s[s_idx] != (*t)[t_idx]) {
          (s[s_idx] < (*t)[t_idx] ? lb : ub) = mid;
          finished = true;
          break;
        }
      }
      if (!finished) (s_idx == s_size && t_idx < t_size ? lb : ub) = mid;
    }
    return ub;
  }
};

}  // namespace emthrm

Back to top page