This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ngthanhtrung23/ACM_Notebook_new
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_D" #include <bits/stdc++.h> using namespace std; #include "../SuffixArray.h" int main() { ios::sync_with_stdio(0); cin.tie(0); string s, pat; int q; cin >> s >> q; auto sa = suffix_array(s, 0, 255); while (q--) { cin >> pat; int cnt = cnt_occurrences(s, sa, pat); cout << (cnt ? 1 : 0) << '\n'; } return 0; }
#line 1 "String/tests/suffix_array_queries.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_D" #include <bits/stdc++.h> using namespace std; #line 1 "String/SuffixArray.h" // Efficient O(N + alphabet_size) time and space suffix array // For ICPC notebook, it's better to copy a shorter code such as // https://github.com/kth-competitive-programming/kactl/blob/main/content/strings/SuffixArray.h // Usage: // - sa = suffix_array(s, 'a', 'z') // - lcp = LCP(s, sa) // lcp[i] = LCP(sa[i], sa[i+1]) // // Tested: // - SA https://judge.yosupo.jp/problem/suffixarray // - SA https://www.spoj.com/problems/SARRAY/ // - LCP https://judge.yosupo.jp/problem/number_of_substrings // Suffix Array {{{ // Copied from https://judge.yosupo.jp/submission/52300 // Helper functions {{{ void induced_sort(const std::vector<int>& vec, int val_range, std::vector<int>& SA, const std::vector<bool>& sl, const std::vector<int>& lms_idx) { std::vector<int> l(val_range, 0), r(val_range, 0); for (int c : vec) { if (c + 1 < val_range) ++l[c + 1]; ++r[c]; } std::partial_sum(l.begin(), l.end(), l.begin()); std::partial_sum(r.begin(), r.end(), r.begin()); std::fill(SA.begin(), SA.end(), -1); for (int i = (int)lms_idx.size() - 1; i >= 0; --i) SA[--r[vec[lms_idx[i]]]] = lms_idx[i]; for (int i : SA) if (i >= 1 && sl[i - 1]) SA[l[vec[i - 1]]++] = i - 1; std::fill(r.begin(), r.end(), 0); for (int c : vec) ++r[c]; std::partial_sum(r.begin(), r.end(), r.begin()); for (int k = (int)SA.size() - 1, i = SA[k]; k >= 1; --k, i = SA[k]) if (i >= 1 && !sl[i - 1]) { SA[--r[vec[i - 1]]] = i - 1; } } std::vector<int> SA_IS(const std::vector<int>& vec, int val_range) { const int n = vec.size(); std::vector<int> SA(n), lms_idx; std::vector<bool> sl(n); sl[n - 1] = false; for (int i = n - 2; i >= 0; --i) { sl[i] = (vec[i] > vec[i + 1] || (vec[i] == vec[i + 1] && sl[i + 1])); if (sl[i] && !sl[i + 1]) lms_idx.push_back(i + 1); } std::reverse(lms_idx.begin(), lms_idx.end()); induced_sort(vec, val_range, SA, sl, lms_idx); std::vector<int> new_lms_idx(lms_idx.size()), lms_vec(lms_idx.size()); for (int i = 0, k = 0; i < n; ++i) if (!sl[SA[i]] && SA[i] >= 1 && sl[SA[i] - 1]) { new_lms_idx[k++] = SA[i]; } int cur = 0; SA[n - 1] = cur; for (size_t k = 1; k < new_lms_idx.size(); ++k) { int i = new_lms_idx[k - 1], j = new_lms_idx[k]; if (vec[i] != vec[j]) { SA[j] = ++cur; continue; } bool flag = false; for (int a = i + 1, b = j + 1;; ++a, ++b) { if (vec[a] != vec[b]) { flag = true; break; } if ((!sl[a] && sl[a - 1]) || (!sl[b] && sl[b - 1])) { flag = !((!sl[a] && sl[a - 1]) && (!sl[b] && sl[b - 1])); break; } } SA[j] = (flag ? ++cur : cur); } for (size_t i = 0; i < lms_idx.size(); ++i) lms_vec[i] = SA[lms_idx[i]]; if (cur + 1 < (int)lms_idx.size()) { auto lms_SA = SA_IS(lms_vec, cur + 1); for (size_t i = 0; i < lms_idx.size(); ++i) { new_lms_idx[i] = lms_idx[lms_SA[i]]; } } induced_sort(vec, val_range, SA, sl, new_lms_idx); return SA; } // }}} template<typename ContainerT = std::string, typename ElemT = unsigned char> std::vector<int> suffix_array(const ContainerT& s, const ElemT first = 'a', const ElemT last = 'z') { std::vector<int> vec(s.size() + 1); std::copy(std::begin(s), std::end(s), std::begin(vec)); for (auto& x : vec) x -= (int)first - 1; vec.back() = 0; auto ret = SA_IS(vec, (int)last - (int)first + 2); ret.erase(ret.begin()); return ret; } // Author: https://codeforces.com/blog/entry/12796?#comment-175287 // Uses kasai's algorithm linear in time and space std::vector<int> LCP(const std::string& s, const std::vector<int>& sa) { int n = s.size(), k = 0; std::vector<int> lcp(n), rank(n); for (int i = 0; i < n; i++) rank[sa[i]] = i; for (int i = 0; i < n; i++, k ? k-- : 0) { if (rank[i] == n - 1) { k = 0; continue; } int j = sa[rank[i] + 1]; while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++; lcp[rank[i]] = k; } lcp[n - 1] = 0; return lcp; } // }}} // Number of distinct substrings {{{ // Tested: // - https://judge.yosupo.jp/problem/number_of_substrings // - https://www.spoj.com/problems/SUBST1/ int64_t cnt_distinct_substrings(const std::string& s) { auto lcp = LCP(s, suffix_array(s, 0, 255)); return s.size() * (int64_t) (s.size() + 1) / 2 - std::accumulate(lcp.begin(), lcp.end(), 0LL); } // }}} // K-th distinct substring {{{ // Tested: // - https://cses.fi/problemset/task/2108 // - https://www.spoj.com/problems/SUBLEX/ // Consider all distinct substring of string `s` in lexicographically increasing // order. Find k-th substring. // // Preprocessing: O(N) // Each query: O(log(N)) // // Returns {start index, length}. If not found -> {-1, -1} std::vector<std::pair<int,int>> kth_distinct_substring( const std::string& s, const std::vector<int64_t>& ks) { if (s.empty()) { return {}; } auto sa = suffix_array(s, 0, 255); auto lcp = LCP(s, sa); int n = s.size(); // for each suffix (in increasing order), we count how many new distinct // substrings it create std::vector<int64_t> n_new_substrs(n); for (int i = 0; i < n; ++i) { int substr_len = n - sa[i]; int new_substr_start = (i > 0 ? lcp[i-1] : 0); n_new_substrs[i] = substr_len - new_substr_start; } std::partial_sum(n_new_substrs.begin(), n_new_substrs.end(), n_new_substrs.begin()); std::vector<std::pair<int,int>> res; for (int64_t k : ks) { if (k > *n_new_substrs.rbegin()) { res.emplace_back(-1, -1); } else { int i = std::lower_bound(n_new_substrs.begin(), n_new_substrs.end(), k) - n_new_substrs.begin(); int new_substr_start = (i > 0 ? lcp[i-1] : 0); if (i > 0) k -= n_new_substrs[i-1]; res.emplace_back(sa[i], new_substr_start + k); } } return res; } // }}} // Count substring occurrences {{{ // given string S and Q queries pat_i, for each query, count how many // times pat_i appears in S // O(min(|S|, |pat|) * log(|S|)) per query // // Tested: // - (yes / no) https://cses.fi/problemset/task/2102 // - (count) https://cses.fi/problemset/task/2103 // - (position; need RMQ) https://cses.fi/problemset/task/2104 int cnt_occurrences(const string& s, const vector<int>& sa, const string& pat) { int n = s.size(), m = pat.size(); assert(n == (int) sa.size()); if (n < m) return 0; auto f = [&] (int start) { // compare S[start..] and pat[0..] for (int i = 0; start + i < n && i < m; ++i) { if (s[start + i] < pat[i]) return true; if (s[start + i] > pat[i]) return false; } return n - start < m; }; auto g = [&] (int start) { for (int i = 0; start + i < n && i < m; ++i) { if (s[start + i] > pat[i]) return false; } return true; }; auto l = std::partition_point(sa.begin(), sa.end(), f); auto r = std::partition_point(l, sa.end(), g); // To find first occurrence, return min of sa in range [l, r) // See https://cses.fi/problemset/task/2104 return std::distance(l, r); } // }}} // Count substring occurrences using hash {{{ // If hash array can be pre-computed, can answer each query in // O(log(|S|) * log(|S| + |pat|) // Tested // - https://oj.vnoi.info/problem/icpc22_mt_b #line 1 "Math/modint.h" // ModInt {{{ template<int MD> struct ModInt { using ll = long long; int x; constexpr ModInt() : x(0) {} constexpr ModInt(ll v) { _set(v % MD + MD); } constexpr static int mod() { return MD; } constexpr explicit operator bool() const { return x != 0; } constexpr ModInt operator + (const ModInt& a) const { return ModInt()._set((ll) x + a.x); } constexpr ModInt operator - (const ModInt& a) const { return ModInt()._set((ll) x - a.x + MD); } constexpr ModInt operator * (const ModInt& a) const { return ModInt()._set((ll) x * a.x % MD); } constexpr ModInt operator / (const ModInt& a) const { return ModInt()._set((ll) x * a.inv().x % MD); } constexpr ModInt operator - () const { return ModInt()._set(MD - x); } constexpr ModInt& operator += (const ModInt& a) { return *this = *this + a; } constexpr ModInt& operator -= (const ModInt& a) { return *this = *this - a; } constexpr ModInt& operator *= (const ModInt& a) { return *this = *this * a; } constexpr ModInt& operator /= (const ModInt& a) { return *this = *this / a; } friend constexpr ModInt operator + (ll a, const ModInt& b) { return ModInt()._set(a % MD + b.x); } friend constexpr ModInt operator - (ll a, const ModInt& b) { return ModInt()._set(a % MD - b.x + MD); } friend constexpr ModInt operator * (ll a, const ModInt& b) { return ModInt()._set(a % MD * b.x % MD); } friend constexpr ModInt operator / (ll a, const ModInt& b) { return ModInt()._set(a % MD * b.inv().x % MD); } constexpr bool operator == (const ModInt& a) const { return x == a.x; } constexpr bool operator != (const ModInt& a) const { return x != a.x; } friend std::istream& operator >> (std::istream& is, ModInt& other) { ll val; is >> val; other = ModInt(val); return is; } constexpr friend std::ostream& operator << (std::ostream& os, const ModInt& other) { return os << other.x; } constexpr ModInt pow(ll k) const { ModInt ans = 1, tmp = x; while (k) { if (k & 1) ans *= tmp; tmp *= tmp; k >>= 1; } return ans; } constexpr ModInt inv() const { if (x < 1000111) { _precalc(1000111); return invs[x]; } int a = x, b = MD, ax = 1, bx = 0; while (b) { int q = a/b, t = a%b; a = b; b = t; t = ax - bx*q; ax = bx; bx = t; } assert(a == 1); if (ax < 0) ax += MD; return ax; } static std::vector<ModInt> factorials, inv_factorials, invs; constexpr static void _precalc(int n) { if (factorials.empty()) { factorials = {1}; inv_factorials = {1}; invs = {0}; } if (n > MD) n = MD; int old_sz = factorials.size(); if (n <= old_sz) return; factorials.resize(n); inv_factorials.resize(n); invs.resize(n); for (int i = old_sz; i < n; ++i) factorials[i] = factorials[i-1] * i; inv_factorials[n-1] = factorials.back().pow(MD - 2); for (int i = n - 2; i >= old_sz; --i) inv_factorials[i] = inv_factorials[i+1] * (i+1); for (int i = n-1; i >= old_sz; --i) invs[i] = inv_factorials[i] * factorials[i-1]; } static int get_primitive_root() { static int primitive_root = 0; if (!primitive_root) { primitive_root = [&]() { std::set<int> fac; int v = MD - 1; for (ll i = 2; i * i <= v; i++) while (v % i == 0) fac.insert(i), v /= i; if (v > 1) fac.insert(v); for (int g = 1; g < MD; g++) { bool ok = true; for (auto i : fac) if (ModInt(g).pow((MD - 1) / i) == 1) { ok = false; break; } if (ok) return g; } return -1; }(); } return primitive_root; } static ModInt C(int n, int k) { _precalc(n + 1); return factorials[n] * inv_factorials[k] * inv_factorials[n-k]; } private: // Internal, DO NOT USE. // val must be in [0, 2*MD) constexpr inline __attribute__((always_inline)) ModInt& _set(ll v) { x = v >= MD ? v - MD : v; return *this; } }; template <int MD> std::vector<ModInt<MD>> ModInt<MD>::factorials = {1}; template <int MD> std::vector<ModInt<MD>> ModInt<MD>::inv_factorials = {1}; template <int MD> std::vector<ModInt<MD>> ModInt<MD>::invs = {0}; // }}} #line 2 "String/hash.h" // Hash {{{ // Usage: // HashGenerator g(MAX_LENGTH) // // auto h = g.hash(s) // g.equals(s, h, l1, r1, s, h, l2, r2) // g.cmp(s, h, l1, r1, s, h, l2, r2) // // Tested: // - https://oj.vnoi.info/problem/substr // - https://oj.vnoi.info/problem/paliny - max palin / binary search // - https://oj.vnoi.info/problem/dtksub - hash<Hash> for unordered_map // - https://oj.vnoi.info/problem/vostr - cmp const int MOD = 1e9 + 7; using modular = ModInt<MOD>; struct Hash { long long x; modular y; Hash operator + (const Hash& a) const { return Hash{x + a.x, y + a.y}; } Hash operator - (const Hash& a) const { return Hash{x - a.x, y - a.y}; } Hash operator * (const Hash& a) const { return Hash{x * a.x, y * a.y}; } Hash operator * (int k) const { return Hash{x*k, y*k}; } Hash& operator += (const Hash& a) { return *this = *this + a; } Hash& operator -= (const Hash& a) { return *this = *this - a; } Hash& operator *= (const Hash& a) { return *this = *this * a; } }; bool operator == (const Hash& a, const Hash& b) { return a.x == b.x && a.y == b.y; } bool operator < (const Hash& a, const Hash& b) { if (a.x != b.x) return a.x < b.x; return a.y.x < b.y.x; } std::ostream& operator << (std::ostream& out, const Hash& h) { out << '(' << h.x << ", " << h.y << ')'; return out; } // hash function for std::unordered_map namespace std { template<> struct hash<Hash> { public: size_t operator() (const Hash& h) const { return h.x * 1000000009 + h.y.x; } }; } struct HashGenerator { HashGenerator(int maxLen, int base = 311) { p.resize(maxLen + 1); p[0] = {1, 1}; for (int i = 1; i <= maxLen; i++) { p[i] = p[i-1] * base; } } template<typename Container> std::vector<Hash> hash(const Container& s) const { std::vector<Hash> res(s.size()); for (size_t i = 0; i < s.size(); i++) { res[i] = p[i] * (int) s[i]; } std::partial_sum(res.begin(), res.end(), res.begin()); return res; } Hash getHash(const std::vector<Hash>& h, int l, int r) const { return __getHash(h, l, r) * p[p.size() - 1 - l]; } // compare [l1, r1] vs [l2, r2] bool equals( const std::vector<Hash>& h1, int l1, int r1, const std::vector<Hash>& h2, int l2, int r2) const { assert(0 <= l1 && l1 <= r1 && r1 < (int) h1.size()); assert(0 <= l2 && l2 <= r2 && r2 < (int) h2.size()); if (r1 - l1 != r2 - l2) return false; return getHash(h1, l1, r1) == getHash(h2, l2, r2); } // Returns length of max common prefix of h1[l1, r1] and h2[l2, r2] // length = 0 -> first character of 2 substrings are different. int maxCommonPrefix( const std::vector<Hash>& h1, int l1, int r1, const std::vector<Hash>& h2, int l2, int r2) const { assert(0 <= l1 && l1 <= r1 && r1 < (int) h1.size()); assert(0 <= l2 && l2 <= r2 && r2 < (int) h2.size()); int len1 = r1 - l1 + 1; int len2 = r2 - l2 + 1; int res = -1, left = 0, right = std::min(len1, len2) - 1; while (left <= right) { int mid = (left + right) / 2; if (equals(h1, l1, l1 + mid, h2, l2, l2 + mid)) { res = mid; left = mid + 1; } else { right = mid - 1; } } return res + 1; /* C++20 auto r = std::views::iota(0, std::min(len1, len2)); auto res = std::ranges::partition_point( r, [&] (int mid) { return equals(h1, l1, l1+mid, h2, l2, l2+mid); }); return *res; */ } // compare s1[l1, r1] and s2[l2, r2] template<typename Container1, typename Container2> int cmp( const Container1& s1, const std::vector<Hash>& h1, int l1, int r1, const Container2& s2, const std::vector<Hash>& h2, int l2, int r2) const { assert(0 <= l1 && l1 <= r1 && r1 < (int) h1.size()); assert(0 <= l2 && l2 <= r2 && r2 < (int) h2.size()); int commonPrefixLen = maxCommonPrefix(h1, l1, r1, h2, l2, r2); char c1 = (l1 + commonPrefixLen <= r1) ? s1[l1 + commonPrefixLen] : 0; char c2 = (l2 + commonPrefixLen <= r2) ? s2[l2 + commonPrefixLen] : 0; return (c1 == c2) ? 0 : ((c1 < c2) ? -1 : 1); } private: std::vector<Hash> p; // DO NOT USE, this doesn't divide by p[l] Hash __getHash(const std::vector<Hash>& h, int l, int r) const { assert(0 <= l && l <= r && r < (int) h.size()); return h[r] - (l == 0 ? Hash{0, 0} : h[l-1]); } }; // }}} #line 216 "String/SuffixArray.h" int cnt_occurrences_hash( const vector<int>& sa, // suffix array const HashGenerator& gen, const string& s, const vector<Hash>& hash_s, // hash of `s`, generated with `gen` const string_view& pat, const vector<Hash>& hash_pat // hash of `pat`, generated with `gen` ) { int n = s.size(), len = pat.size(); assert(len == (int) hash_pat.size()); assert(n == (int) sa.size()); if (n < len) return 0; // f(start) = compare string S[start..] and pat[0..len-1] auto f = [&] (int start) { return gen.cmp( s, hash_s, start, n-1, pat, hash_pat, 0, len-1) < 0; }; // g(start) = true if S[start..] == pat[0..] auto g = [&] (int start) { int max_len = std::min(n - start, len); return gen.cmp( s, hash_s, start, start + max_len - 1, pat, hash_pat, 0, max_len-1) == 0; }; auto l = std::partition_point(sa.begin(), sa.end(), f); auto r = std::partition_point(l, sa.end(), g); return std::distance(l, r); } // }}} // Returns length of LCS of strings s & t {{{ // O(N) // Tested: // - https://www.spoj.com/problems/LCS/ // - https://www.spoj.com/problems/ADAPHOTO/ int longestCommonSubstring(const string& s, const string& t) { char c = 127; string combined = s + c + t; auto sa = suffix_array(combined, 0, 127); auto lcp = LCP(combined, sa); // s -> 0 .. |s|-1 // 255 -> |s| // t -> |s|+1 .. int ls = s.size(), lcombined = combined.size(); auto is_s = [&] (int id) { return sa[id] < ls; }; auto is_t = [&] (int id) { return sa[id] > ls; }; assert(sa[lcombined - 1] == ls); int res = 0; for (int i = 0; i < lcombined - 2; ++i) { if ((is_s(i) && is_t(i+1)) || (is_s(i+1) && is_t(i))) { res = max(res, lcp[i]); } } return res; } // }}} // Returns length of LCS of n strings {{{ // Tested: // - https://www.spoj.com/problems/LCS2/ // - https://www.spoj.com/problems/LONGCS #line 1 "DataStructure/RMQ.h" // RMQ {{{ // // Sparse table // Usage: // RMQ<int, _min> st(v); // // Note: // - doesn't work for empty range // // Tested: // - https://judge.yosupo.jp/problem/staticrmq template<class T, T (*op) (T, T)> struct RMQ { RMQ() = default; RMQ(const vector<T>& v) : t{v}, n{(int) v.size()} { for (int k = 1; (1<<k) <= n; ++k) { t.emplace_back(n - (1<<k) + 1); for (int i = 0; i + (1<<k) <= n; ++i) { t[k][i] = op(t[k-1][i], t[k-1][i + (1<<(k-1))]); } } } // get range [l, r-1] // doesn't work for empty range T get(int l, int r) const { assert(0 <= l && l < r && r <= n); int k = __lg(r - l); return op(t[k][l], t[k][r - (1<<k)]); } private: vector<vector<T>> t; int n; }; template<class T> T _min(T a, T b) { return b < a ? b : a; } template<class T> T _max(T a, T b) { return a < b ? b : a; } // }}} #line 281 "String/SuffixArray.h" int longestCommonSubstring(const std::vector<std::string> strs) { char c = 127; string combined = ""; vector<int> ids; for (size_t i = 0; i < strs.size(); ++i) { const auto& s = strs[i]; combined += s; while (ids.size() < combined.size()) ids.push_back(i); combined += c; ids.push_back(-1); --c; } auto sa = suffix_array(combined, 0, 127); auto lcp = LCP(combined, sa); RMQ<int, _min> rmq(lcp); // count frequency of i-th string in current window std::vector<int> cnt(strs.size(), 0); int strs_in_window = 0; auto add = [&] (int i) { if (i < 0) return; ++cnt[i]; if (cnt[i] == 1) ++strs_in_window; }; auto rem = [&] (int i) { if (i < 0) return; --cnt[i]; if (cnt[i] == 0) --strs_in_window; }; int i = 0, j = -1; int lcombined = combined.size(); int n = strs.size(); int res = 0; while (i < lcombined - 1) { while (j + 1 < lcombined - 1 && strs_in_window < n) { ++j; add(ids[sa[j]]); } if (strs_in_window == n) { res = max(res, rmq.get(i, j)); } rem(ids[sa[i]]); ++i; } return res; } // }}} #line 7 "String/tests/suffix_array_queries.test.cpp" int main() { ios::sync_with_stdio(0); cin.tie(0); string s, pat; int q; cin >> s >> q; auto sa = suffix_array(s, 0, 255); while (q--) { cin >> pat; int cnt = cnt_occurrences(s, sa, pat); cout << (cnt ? 1 : 0) << '\n'; } return 0; }