文字列/接尾辞配列
(test/string/suffix_array.test.cpp)

• View this file on GitHub
• Last update: 2023-07-07 02:42:02+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B

Depends on

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

Code

/*
 * @title 文字列/接尾辞配列
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B
 */

#include <iostream>
#include <string>

#include "emthrm/string/suffix_array.hpp"

int main() {
  std::string t, p;
  std::cin >> t >> p;
  for (const int ans : emthrm::SuffixArray<>(t).match(&p)) {
    std::cout << ans << '\n';
  }
  return 0;
}

#line 1 "test/string/suffix_array.test.cpp"
/*
 * @title 文字列/接尾辞配列
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B
 */

#include <iostream>
#include <string>

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



#include <algorithm>
#include <numeric>
#line 7 "include/emthrm/string/suffix_array.hpp"
#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


#line 11 "test/string/suffix_array.test.cpp"

int main() {
  std::string t, p;
  std::cin >> t >> p;
  for (const int ans : emthrm::SuffixArray<>(t).match(&p)) {
    std::cout << ans << '\n';
  }
  return 0;
}

Back to top page