Japan Alumni Group Summer Camp 2014 Day 4 F: Longest Match
問題
RUPC 2016 の時に @public_sate さんに教えてもらった。
F: Longest Match - Japan Alumni Group Summer Camp 2014 Day 4 | AtCoder
解法
コード
#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; } 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); } }; class SuffixArray { private: string s; SuffixArray() {} public: vector<int> sa; SuffixArray(string const &s) { this->s = s; sa.resize(s.size() + 1); build(); } void build() { int n = s.length(); vector<int> rank(n + 1); for (int i = 0; i < n + 1; ++i) { sa[i] = i; rank[i] = i < n ? s[i] : -1; } for (int k = 1; k <= n; k *= 2) { auto compare = [&](int i, int j) { int ri = i + k <= n ? rank[i + k] : -1; int rj = j + k <= n ? rank[j + k] : -1; return make_pair(rank[i], ri) < make_pair(rank[j], rj); }; sort(sa.begin(), sa.end(), compare); vector<int> dp(n + 1); dp[sa[0]] = 0; for (int i = 0; i < n; ++i) dp[sa[i + 1]] = dp[sa[i]] + compare(sa[i], sa[i + 1]); rank = dp; } sa.erase(sa.begin()); } int lower_bound(const string &t) { int a = -1, b = s.size() - 1; while (b - a > 1) { int c = (a + b) / 2; if (s.compare(sa[c], t.size(), t) < 0) a = c; else b = c; } return s.compare(sa[b], t.size(), t) == 0 ? b : -1; } int upper_bound(const string &t) { int a = -1, b = s.size(); while (b - a > 1) { int c = (a + b) / 2; if (s.compare(sa[c], t.size(), t) <= 0) a = c; else b = c; } return b; } }; int main() { cin.tie(0); ios::sync_with_stdio(false); string S; cin >> S; int N = S.size(); SuffixArray 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]); } 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; } } }