Suffix Array の練習問題
問題概要
英小文字からなる文字列 と、 個のクエリが与えられる。
各クエリでは 2 つの文字列 が与えられる。
文字列 の連続する部分文字列であって、 で始まり、 で終わるものの中で、最長の長さを答えよ。ただし、そのような部分文字列が存在しない場合には 0 と答えよ。
制約
- 各クエリで与えられる文字列 , の長さの合計は 以下
考えたこと
Suffix Array を用いて文字列検索する手法がある。それを応用して今回の問題は解ける。なお、Suffix Array を構築したあとでは、文字列 を検索するのに要する計算量は であり、非常に高速である。
そもそも が に含まれていなければ、答えは 0 としてよい。
まず、文字列 から始まる suffix のうち、最小の添字 xres
を求める。Suffix Array 上では、文字列 から始まる suffix は連続した区間になる。その区間の左端と右端は Suffix Array の lower_bound によって求められる (蟻本 P.338 参照)。その区間内での、文字列 の index の最小値を求めれば良い。これは RMQ を用いて高速に求められる。
次に、文字列 から始まる suffix のうち、最大の添字 yres
を求める。これも同様に RMQ を用いて求められる。
求める答えは次の通り。
xres > yres
の場合:答えは0
xres + x.size() > yres + y.size()
の場合:答えは0
- それ以外:答えは
yres - xres + y.size();
コード
計算量は、クエリに登場する文字列の長さの合計値を として、
- Suffix Array の構築:
- 各クエリの処理:
となる。
#include <bits/stdc++.h> using namespace std; // Sparse Table template<class MeetSemiLattice> struct SparseTable { vector<vector<MeetSemiLattice> > dat; vector<int> height; SparseTable() { } SparseTable(const vector<MeetSemiLattice> &vec) { init(vec); } void init(const vector<MeetSemiLattice> &vec) { int n = (int)vec.size(), h = 0; while ((1<<h) < n) ++h; dat.assign(h, vector<MeetSemiLattice>(1<<h)); height.assign(n+1, 0); for (int i = 2; i <= n; i++) height[i] = height[i>>1]+1; for (int i = 0; i < n; ++i) dat[0][i] = vec[i]; for (int i = 1; i < h; ++i) for (int j = 0; j < n; ++j) dat[i][j] = min(dat[i-1][j], dat[i-1][min(j+(1<<(i-1)),n-1)]); } MeetSemiLattice get(int a, int b) { return min(dat[height[b-a]][a], dat[height[b-a]][b-(1<<height[b-a])]); } }; // SA-IS (O(N)) template<class Str> struct SuffixArray { // data Str str; vector<int> sa; // sa[i] : the starting index of the i-th smallest suffix (i = 0, 1, ..., n) vector<int> rank; // rank[sa[i]] = i vector<int> lcp; // lcp[i]: the lcp of sa[i] and sa[i+1] (i = 0, 1, ..., n-1) SparseTable<int> st; // use for calcultating lcp(i, j) // getter int& operator [] (int i) { return sa[i]; } vector<int> get_sa() { return sa; } vector<int> get_rank() { return rank; } vector<int> get_lcp() { return lcp; } // constructor SuffixArray(const Str& str_) : str(str_) { build_sa(); } void init(const Str& str_) { str = str_; build_sa(); } void build_sa() { vector<int> s; for (int i = 0; i < (int)str.size(); ++i) { s.push_back(str[i] + 1); } s.push_back(0); sa = sa_is(s); calcLCP(s); buildSparseTable(); } // SA-IS // upper: # of characters vector<int> sa_is(vector<int> &s, int upper = 256) { int N = (int)s.size(); if (N == 0) return {}; else if (N == 1) return {0}; else if (N == 2) { if (s[0] < s[1]) return {0, 1}; else return {1, 0}; } vector<int> isa(N); vector<bool> ls(N, false); for (int i = N - 2; i >= 0; --i) { ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]); } vector<int> sum_l(upper + 1, 0), sum_s(upper + 1, 0); for (int i = 0; i < N; ++i) { if (!ls[i]) ++sum_s[s[i]]; else ++sum_l[s[i] + 1]; } for (int i = 0; i <= upper; ++i) { sum_s[i] += sum_l[i]; if (i < upper) sum_l[i + 1] += sum_s[i]; } auto induce = [&](const vector<int> &lms) -> void { fill(isa.begin(), isa.end(), -1); vector<int> buf(upper + 1); copy(sum_s.begin(), sum_s.end(), buf.begin()); for (auto d: lms) { if (d == N) continue; isa[buf[s[d]]++] = d; } copy(sum_l.begin(), sum_l.end(), buf.begin()); isa[buf[s[N - 1]]++] = N - 1; for (int i = 0; i < N; ++i) { int v = isa[i]; if (v >= 1 && !ls[v - 1]) { isa[buf[s[v - 1]]++] = v - 1; } } copy(sum_l.begin(), sum_l.end(), buf.begin()); for (int i = N - 1; i >= 0; --i) { int v = isa[i]; if (v >= 1 && ls[v - 1]) { isa[--buf[s[v - 1] + 1]] = v - 1; } } }; vector<int> lms, lms_map(N + 1, -1); int M = 0; for (int i = 1; i < N; ++i) { if (!ls[i - 1] && ls[i]) { lms_map[i] = M++; } } lms.reserve(M); for (int i = 1; i < N; ++i) { if (!ls[i - 1] && ls[i]) { lms.push_back(i); } } induce(lms); if (M) { vector<int> lms2; lms2.reserve(isa.size()); for (auto v: isa) { if (lms_map[v] != -1) lms2.push_back(v); } int rec_upper = 0; vector<int> rec_s(M); rec_s[lms_map[lms2[0]]] = 0; for (int i = 1; i < M; ++i) { int l = lms2[i - 1], r = lms2[i]; int nl = (lms_map[l] + 1 < M) ? lms[lms_map[l] + 1] : N; int nr = (lms_map[r] + 1 < M) ? lms[lms_map[r] + 1] : N; bool same = true; if (nl - l != nr - r) same = false; else { while (l < nl) { if (s[l] != s[r]) break; ++l, ++r; } if (l == N || s[l] != s[r]) same = false; } if (!same) ++rec_upper; rec_s[lms_map[lms2[i]]] = rec_upper; } auto rec_sa = sa_is(rec_s, rec_upper); vector<int> sorted_lms(M); for (int i = 0; i < M; ++i) { sorted_lms[i] = lms[rec_sa[i]]; } induce(sorted_lms); } return isa; } // find min id that str.substr(sa[id]) >= T int lower_bound(const Str& T) { int left = -1, right = sa.size(); while (right - left > 1) { int mid = (left + right) / 2; if (str.compare(sa[mid], string::npos, T) < 0) left = mid; else right = mid; } return right; } // find min id that str.substr(sa[id], T.size()) > T int upper_bound(const Str& T) { int left = -1, right = sa.size(); while (right - left > 1) { int mid = (left + right) / 2; if (str.compare(sa[mid], T.size(), T) <= 0) left = mid; else right = mid; } return right; } // search bool is_contain(const Str& T) { int lb = lower_bound(T); if (lb >= sa.size()) return false; return str.compare(sa[lb], T.size(), T) == 0; } // find lcp void calcLCP(const vector<int> &s) { int N = (int)s.size(); rank.assign(N, 0), lcp.assign(N, 0); for (int i = 0; i < N; ++i) rank[sa[i]] = i; int h = 0; for (int i = 0; i < N - 1; ++i) { int pi = sa[rank[i] - 1]; if (h > 0) --h; for (; pi + h < N && i + h < N; ++h) { if (s[pi + h] != s[i + h]) break; } lcp[rank[i] - 1] = h; } } // build sparse table for calculating lcp void buildSparseTable() { st.init(lcp); } // calc lcp of str.sutstr(a) and str.substr(b) int getLCP(int a, int b) { return st.get(min(rank[a], rank[b]), max(rank[a], rank[b])); } }; void solveAOJ2644() { // Suffix Array の構築 string S; cin >> S; SuffixArray<string> suf(S); vector<int> sa = suf.get_sa(); // Suffix Array の区間に関する RMQ SparseTable<int> min_st(sa); for (auto& v : sa) v = -v; SparseTable<int> max_st(sa); auto solve = [&](const string& x, const string& y) -> int { if (!suf.is_contain(x) || !suf.is_contain(y)) { return 0; } int xl = suf.lower_bound(x); int xr = suf.upper_bound(x); int yl = suf.lower_bound(y); int yr = suf.upper_bound(y); int xres = min_st.get(xl, xr); int yres = -max_st.get(yl, yr); if (xres > yres || xres + x.size() > yres + y.size()) return 0; else return yres - xres + (int)y.size(); }; int Q; cin >> Q; while (Q--) { string x, y; cin >> x >> y; cout << solve(x, y) << endl; } } int main() { solveAOJ2644(); }