Beautiful Words

#include <bits/stdc++.h>
using namespace std;

const int64_t MOD = (1LL<<61)-1;
const int base = 31;

int64_t p[100005];

int64_t modMul(int64_t a, int64_t b) {
  return (__int128_t)a*b%MOD;
}

struct StringHashing {
    inline int getInt(char c) {
        return (c-'a'+1);
    }
    /*
        hs[i] = s[0]*p^(i) + s[1]*p(i-1) + ... + s[i-1]*p + s[i]
    */
    vector<int64_t> hs;
    StringHashing () {}
    StringHashing (const string &s) {
        int n = s.size();
        hs.resize(n);
        hs[0] = getInt(s[0]);
        for (int i = 1; i < n; ++i) {
            hs[i] = modMul(hs[i-1], base) + getInt(s[i]);
      if (hs[i] >= MOD) {
        hs[i] -= MOD;
      }
        }
    }
    /*
        hs[i..j] = hs[j] - hs[i-1] * p^(j-i+1)
    */
    int64_t getValue(int l, int r) {
        if (l > r) return -1;
        int64_t res = hs[r];
        if (l > 0) {
      res -= modMul(p[r-l+1], hs[l-1]);
      if (res < 0) {
        res += MOD;
      }
    }
        return res;
    }
};

int n, m;
string a, aux;
vector<string> s;
vector<int64_t> vec;
StringHashing sh, sh1;

bool f(int k) {

  vec.clear();
  for (int i = 0; i < (int)aux.size()-k+1; ++i) {
    vec.push_back(sh1.getValue(i, i+k-1));
  }

  sort(vec.begin(), vec.end());

  vector<int> vet(2*n+1, 0);

  for (int i = 0; i < 2*n-k+1; ++i) {
    if (binary_search(vec.begin(), vec.end(), sh.getValue(i, i+k-1))) {
      int l = max(0, i+k-n);
      int r = i;
      ++vet[l];
      --vet[r+1];
    }
  }

  bool ok = vet[0];
  for (int i = 1; i < n; ++i) {
    vet[i] += vet[i-1];
    ok &= (vet[i] > 0);
  }

  return ok;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);

  p[0] = 1;
  for (int i = 1; i < 100002; ++i) {
    p[i] = modMul(p[i-1], base);
  }

  cin >> n >> m;
  cin >> a;
  a += a;

  s.resize(m);
  int lo = 1, hi = 0, mid = -1, ans = 0;
  for (int i = 0; i < m; ++i) {
    cin >> s[i];
    hi = max(hi, (int)s[i].size());
  }
  hi = min(hi, n);

  for (string &sr : s) {
    aux += '#' + sr;
  }

  sh1 = StringHashing(aux);
  sh = StringHashing(a);

  while (lo <= hi) {
    mid = (lo + hi) / 2;
    if (f(mid)) {
      ans = mid;
      lo = mid+1;
    } else {
      hi = mid-1;
    }
  }

  cout << ans << '\n';
}