Untitled
unknown
plain_text
a month ago
2.6 kB
3
Indexable
Never
#include <bits/stdc++.h> using namespace std; const int MAX_N = 100005; const int MAX_M = 10005; const long long BASE = 37; const long long MOD1 = 1000000007; const long long MOD2 = 1000000009; long long powerBase1[MAX_N], powerBase2[MAX_N]; struct Hash { int len; vector<long long> val1, val2; void init(string s) { len = s.length(); s = '0' + s; val1.assign(len + 1, 0); val2.assign(len + 1, 0); for (int i = 1; i <= len; i++) { val1[i] = (val1[i - 1] * BASE + (s[i] - 'a')) % MOD1; val2[i] = (val2[i - 1] * BASE + (s[i] - 'a')) % MOD2; } } pair<int, int> get(int left, int right) { return make_pair(int((val1[right] - val1[left - 1] * powerBase1[right - left + 1] + MOD1 * MOD1) % MOD1), int((val2[right] - val2[left - 1] * powerBase2[right - left + 1] + MOD2 * MOD2) % MOD2)); } }; void prepare_hash() { powerBase1[0] = 1; powerBase2[0] = 1; for (int i = 1; i < MAX_N; i++) { powerBase1[i] = powerBase1[i - 1] * BASE % MOD1; powerBase2[i] = powerBase2[i - 1] * BASE % MOD2; } } int n, m; string str; string arr[MAX_M]; Hash hashCode; Hash hashCodeArr[MAX_N]; void initialize() { str = str + str; hashCode.init(str); for (int id = 1; id <= m; id++) { hashCodeArr[id].init(arr[id]); } } bool check(int length) { set<pair<int, int>> hashCodeOfLength; for (int id = 1; id <= m; id++) { for (int i = 1; i <= hashCodeArr[id].len - length + 1; i++) { hashCodeOfLength.insert(hashCodeArr[id].get(i, i + length - 1)); } } int last = 0; for (int i = 1; i <= n * 2 - length + 1; i++) { if (hashCodeOfLength.count(hashCode.get(i, i + length - 1))) { last = i; } else if (i - last >= n - length + 1) { return true; } } return false; } int binarySearch(int left, int right) { while (left <= right) { int mid = (left + right) / 2; check(mid) ? right = mid - 1 : left = mid + 1; } return right; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); freopen("minstr.inp", "r", stdin); freopen("minstr.out", "w", stdout); prepare_hash(); cin >> n >> m; cin >> str; for (int i = 1; i <= m; i++) { cin >> arr[i]; } initialize(); int answer = binarySearch(1, n); cout << answer; return 0; }
Leave a Comment