Untitled
unknown
plain_text
a month ago
2.9 kB
1
Indexable
Never
#include <bits/stdc++.h> using namespace std; #define ll long long #define EPS 1e-9 #define mod 1000000007 // #define mod 998244353 #define over 10000000000 #define sz(m) (ll)(m.size()) #define ceil(n, m) (((n) / (m)) + ((n) % (m) ? 1 : 0)) #define fixed(n) fixed << setprecision(n) const ll inf = 1e18 + 5; // vector< vector <int> > nums( n , vector<int> (m)) ; // priority_queue<int, vector<int>, greater<int> > pq ; template <typename T = int> istream &operator>>(istream &in, vector<T> &v) { for (T &i : v) in >> i; return in; } template <typename T = int> ostream &operator<<(ostream &out, const vector<T> &v) { for (const T &x : v) out << x << ' '; return out; } void lol() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin), freopen("outputt.txt", "w", stdout), freopen("error.txt", "w", stderr); #endif } double log(double base, double x) { return (log(x) / log(base)); } int dx[4] = {1, 0, 0, -1}; int dy[4] = {0, 1, -1, 0}; ///////////////////////////////////////////////////////// const int N = 5e6 + 10; int p1 = 107, p2 = 277; int pw1[N + 1], inv1[N + 1], pre1[N + 1], pw2[N + 1], inv2[N + 1], pre2[N + 1]; int add(int a, int b) { return (0LL + a % mod + b % mod + mod) % mod; } int mul(int a, int b) { return (1LL * a % mod * b % mod) % mod; } int exp(int x, int n, int m) { x %= m; int res = 1; while (n > 0) { if (n % 2 == 1) { res = mul(res, x); } x = mul(x, x); n /= 2; } return res % m; } void hashh() { pw1[0] = 1, inv1[0] = 1, pw2[0] = 1, inv2[0] = 1; for (int i = 1; i <= N; i++) { pw1[i] = mul(pw1[i - 1], p1); pw2[i] = mul(pw2[i - 1], p2); inv1[i] = exp(pw1[i], mod - 2, mod); inv2[i] = exp(pw2[i], mod - 2, mod); // cout << pw1[i] << ' ' << inv1[i] << '\n'; } } void pre_hash(string &s) { int val1 = 0, val2 = 0; for (int i = 0; i < s.size(); i++) { val1 = add(val1, mul(s[i] - 'a' + 1, pw1[i])); val2 = add(val2, mul(s[i] - 'a' + 1, pw2[i])); pre1[i] = val1, pre2[i] = val2; } } pair<int, int> get_hash_range(int l, int r) { if (l == 0) return {pre1[r], pre2[r]}; return {mul(inv1[l], add(pre1[r], -pre1[l - 1])), mul(inv2[l], add(pre2[r], -pre2[l - 1]))}; } int bs(int l, int r, int x, int y) { int lw = 0, hi = min(r - l + 1, y - x + 1); int best = 0; while (lw <= hi) { int mid = (lw + hi) / 2; if (get_hash_range(l, mid - 1) == get_hash_range(x, x + mid - 1)) { best = mid; lw = mid + 1; } else hi = mid - 1; } return best; } int main() { lol(); hashh(); string s; cin >> s; pre_hash(s); int n = s.size(); int t = 1; cin >> t; while (t--) { int p; cin >> p; cout << bs(0, p - 1, p, n - 1) << '\n'; } }