nord vpnnord vpn
Ad

Untitled

mail@pastecode.io avatar
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';
  }
}

nord vpnnord vpn
Ad