Untitled

#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;
}