Japan Alumni Group Summer Camp 2014 Day 4 F: Longest Match (SA-IS)
hirokazu さんの SA-IS ライブラリをコピペさせてもらった。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; template <typename T> std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) { if (!v.empty()) { out << '['; std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", ")); out << "\b\b]"; } return out; } template <class T, class U> void chmin(T &t, U f) { if (t > f) t = f; } template <class T, class U> void chmax(T &t, U f) { if (t < f) t = f; } class SuffixArrayIS { string text; public: vector<int> sa; private: static bool eq(const vector<int> &v, int idx1, int idx2, const vector<bool> &type) { if (v[idx1] != v[idx2]) return false; int end = v.size() - 1; for (int i = 1;; i++) { if (v[idx1 + i] != v[idx2 + i]) return false; if (idx1 + i == end || (type[idx1 + i - 1] && !type[idx1 + i])) return idx2 + i == end || (type[idx2 + i - 1] && !type[idx2 + i]); else if (idx2 + i == end || (type[idx2 + i - 1] && !type[idx2 + i])) return false; } return true; } template <bool erase> static inline void Lsort(const vector<int> &v, const vector<bool> &type, vector<int> &bucket, vector<int> &rank_less) { for (int i = 0; i < (int)bucket.size(); i++) { if (bucket[i] > 0 && type[bucket[i] - 1]) { bucket[rank_less[v[bucket[i] - 1]]++] = bucket[i] - 1; if (erase) bucket[i] = -1; } } } template <bool erase> static inline void Ssort(const vector<int> &v, const vector<bool> &type, vector<int> &bucket, vector<int> &rank_less_eq) { for (int i = bucket.size() - 1; i >= 0; i--) { if (bucket[i] > 0 && !type[bucket[i] - 1]) { bucket[--rank_less_eq[v[bucket[i] - 1]]] = bucket[i] - 1; if (erase) bucket[i] = -1; } } } static vector<int> induced_sorting(const vector<int> &v, int alpha) { vector<int> bucket(v.size()); vector<int> rank(alpha), c(alpha); vector<bool> type(v.size()); // false=>S,true=>L vector<int> lmsidx, lmsord; type.back() = true; for (int i = v.size() - 2; i >= 0; i--) { if (v[i] < v[i + 1]) type[i] = false; else if (v[i] > v[i + 1]) type[i] = true; else type[i] = type[i + 1]; } for (int i = 0; i < (int)v.size(); i++) rank[v[i]]++; for (int i = 1; i < alpha; i++) rank[i] += rank[i - 1]; // sorting LMS-substring fill(bucket.begin(), bucket.end(), -1); int lmscnt = 0, idx = -1; copy(rank.begin(), rank.end(), c.begin()); for (int i = 1; i < (int)v.size(); i++) { if (type[i - 1] && !type[i]) { // LMS if (lmscnt++) bucket[--c[v[i]]] = i; idx = i; } } if (2 <= lmscnt) { copy(rank.begin(), rank.begin() + alpha - 1, c.begin() + 1); c[0] = 0; bucket[c[v.back()]++] = v.size() - 1; Lsort<true>(v, type, bucket, c); copy(rank.begin(), rank.end(), c.begin()); Ssort<true>(v, type, bucket, c); for (int i = 0; i < (int)bucket.size(); i++) if (bucket[i] > 0) lmsidx.push_back(bucket[i]); if (!lmsidx.empty()) { lmsord.resize(lmsidx.size()); lmsord[0] = 0; for (int i = 1; i < (int)lmsidx.size(); i++) { if (eq(v, lmsidx[i - 1], lmsidx[i], type)) lmsord[i] = lmsord[i - 1]; else lmsord[i] = lmsord[i - 1] + 1; } if (lmsord.back() + 1 != lmsord.size()) { vector<int> lmssuffix; fill(bucket.begin(), bucket.end(), -1); for (int i = 0; i < (int)lmsidx.size(); i++) { if (lmsidx[i]) bucket[lmsidx[i]] = lmsord[i]; } lmsidx.clear(); for (int i = 0; i < (int)bucket.size(); i++) { if (bucket[i] != -1) { lmssuffix.push_back(bucket[i]); lmsidx.push_back(i); } } vector<int> lmssa(induced_sorting(lmssuffix, lmsord.back() + 1)); for (int i = 0; i < (int)lmsidx.size(); i++) { lmsord[i] = lmsidx[lmssa[i]]; } lmsidx.swap(lmsord); } lmsord.clear(); } } else if (1 == lmscnt) { lmsidx.push_back(idx); } // ended sorting LMS-substring fill(bucket.begin(), bucket.end(), -1); copy(rank.begin(), rank.end(), c.begin()); for (int i = lmsidx.size() - 1; i >= 0; i--) bucket[--c[v[lmsidx[i]]]] = lmsidx[i]; copy(rank.begin(), rank.begin() + alpha - 1, c.begin() + 1); c[0] = 0; bucket[c[v.back()]++] = v.size() - 1; Lsort<false>(v, type, bucket, c); copy(rank.begin(), rank.end(), c.begin()); Ssort<false>(v, type, bucket, c); return bucket; } public: SuffixArrayIS(const string &s) { build(s); } const string &get_text() const { return text; } void build(const string &s) { text = s; vector<int> v(s.size()); for (int i = 0; i < (int)s.size(); i++) v[i] = s[i] - 'a'; sa = induced_sorting(v, 26); } int lower_bound(string &s) { int a = -1, b = text.size() - 1; while (b - a > 1) { int c = (a + b) / 2; if (text.compare(sa[c], s.size(), s) < 0) a = c; else b = c; } return text.compare(sa[b], s.size(), s) == 0 ? b : -1; } int upper_bound(string &s) { int a = -1, b = text.size(); while (b - a > 1) { int c = (a + b) / 2; if (text.compare(sa[c], s.size(), s) <= 0) a = c; else b = c; } return b; } string nth_suffix(int k) const { return text.substr(sa[k]); } }; struct RMQ { static const int N = 1 << 20; vector<long long> seg; RMQ() : seg(N * 2, (long long)1e18) {} void update(int k, long long value) { seg[k += N - 1] = value; while (k > 0) { k = (k - 1) / 2; seg[k] = min(seg[k * 2 + 1], seg[k * 2 + 2]); } } //[a, b) long long query(int a, int b, int k = 0, int l = 0, int r = N) { if (r <= a || b <= l) return 1e18; if (a <= l && r <= b) return seg[k]; long long x = query(a, b, k * 2 + 1, l, (l + r) / 2); long long y = query(a, b, k * 2 + 2, (l + r) / 2, r); return min(x, y); } }; int main() { cin.tie(0); ios::sync_with_stdio(false); string S; cin >> S; int N = S.size(); SuffixArrayIS sa(S), revsa(string(S.rbegin(), S.rend())); RMQ rmq, rev; for (int i = 0; i < N; i++) { rmq.update(i, sa.sa[i]); rev.update(i, revsa.sa[i]); } cerr << sa.sa << endl; int M; cin >> M; while (M--) { string x, y; cin >> x >> y; reverse(y.begin(), y.end()); int low = sa.lower_bound(x); if (low == -1) { cout << 0 << endl; continue; } int up = sa.upper_bound(x); int rlow = revsa.lower_bound(y); if (rlow == -1) { cout << 0 << endl; continue; } int rup = revsa.upper_bound(y); int s = rmq.query(low, up); int t = N - rev.query(rlow, rup); if (s + x.size() <= t && s <= t - y.size()) { cout << t - s << endl; } else { cout << 0 << endl; } } }
