Untitled
unknown
plain_text
a month ago
3.0 kB
2
Indexable
Never
#include <iostream> #include <array> #include <vector> #include <algorithm> #include <set> #include <cmath> #include <queue> #include <map> #include <cassert> #include <iomanip> #include <cstring> #include <stack> #include <bitset> using namespace std; #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); void count_sort(vector<int> &p, vector<int> &c){ int n = p.size(); vector<int> cnt(n), pos(n), new_p(n); for (auto &x : c){ cnt[x]++; } pos[0] = 0; for (int i = 1 ; i < n; ++i) pos[i] = pos[i - 1] + cnt[i - 1]; for (auto &x : p){ int i = c[x]; new_p[pos[i]] = x; pos[i]++; } p = new_p; } vector<int>p, c; void suffix_array(string s){ s += '$'; int n = s.size(); p.resize(n), c.resize(n); { vector<pair<char, int>> v(n); for (int i = 0 ; i < n; ++i) v[i] = make_pair(s[i], i); sort(v.begin(), v.end()); for (int i = 0; i < n; ++i) p[i] = v[i].second; /// The ith smallest lexo string starts at index p[i] c[p[0]] = 0; for (int i = 1; i < n; ++i){ if (v[i].first == v[i - 1].first) c[p[i]] = c[p[i - 1]]; else c[p[i]] = c[p[i - 1]] + 1; } } int k = 0; while((1 << k) < n){ for (int i = 0 ; i < n; ++i) p[i] = (p[i] - (1 << k) + n) % n; /// Sort it based on the second; count_sort(p, c); vector<int>new_c(n); new_c[p[0]] = 0; for (int i = 1; i < n; ++i){ pair<int,int> prev = make_pair(c[p[i - 1]], c[(p[i - 1] + (1 << k)) % n]); pair<int,int> cur = make_pair(c[p[i]], c[(p[i] + (1 << k)) % n]); if (cur == prev){ new_c[p[i]] = new_c[p[i - 1]]; } else new_c[p[i]] = new_c[p[i - 1]] + 1; } c = new_c; ++k; } } void solve(){ string s; cin >> s; int n = s.size(); suffix_array(s); int q; cin >> q; while(q--){ string t; cin >> t; int cur_sz = t.size(); int l = 1, r = n, mid, ans = n + 1; while(l <= r){ mid = (l + r) >> 1; string cur = s.substr(p[mid], min(cur_sz, n - p[mid])); if (cur >= t){ r = mid - 1; ans = mid; } else { l = mid + 1; } } l = ans, r = n; int fans = 0; while (l <= r){ mid = (l + r) >> 1; string cur = s.substr(p[mid], min(cur_sz, n - p[mid])); if (cur > t){ r = mid - 1; } else { fans = mid - ans + 1; l = mid + 1; } } cout << fans << '\n'; } } int main(){ fast; int t = 1; //cin >> t; for (int i = 1; i <= t; ++i){ solve(); if (i != t) cout << '\n'; } }
Leave a Comment