LP7456.cpp

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

#define int long long
#define pb push_back
using PII = pair<int, int>;
const int N = 3e5+10, INF = 1e18;
int n;
string s;

int tr[N][26], mark[N], fail[N], idx;
vector<int> G[N];

void insert(const string& s) {
    int u = 0;
    for (char c: s) {
        int p = c - 'a';
        if (!tr[u][p]) tr[u][p] = ++idx;
        u = tr[u][p];
    }
    mark[u] = s.size();
}

void build() {
    queue<int> q;
    for (int i = 0; i < 26; i++) if (tr[0][i]) q.push(tr[0][i]);

    while (q.size()) {
        int fa = q.front(); q.pop();
        for (int i = 0; i < 26; i++) {
            int& u = tr[fa][i];
            if (u) fail[u] = tr[fail[fa]][i], q.push(u);
            else u = tr[fail[fa]][i];
        }
    }

    for (int i = 1; i <= idx; i++) G[fail[i]].pb(i);
}

void dfs(int u, int m) {
    mark[u] = m;
    for (int to : G[u]) {
        if (mark[to]) dfs(to, mark[to]);
        else dfs(to, m);
    }
}

#define Mid ((L+R) >> 1)
#define ls (u<<1)
#define rs (u<<1|1)

int mn[N<<2], leaf[N];
void pushup(int u) {
    mn[u] = min(mn[ls], mn[rs]);
}

void build(int u, int L, int R) {
    if (L == R) return mn[u] = INF, leaf[L] = u, void();
    build(ls, L, Mid);
    build(rs, Mid+1, R);
    pushup(u);
}

void modify(int p, int k) {
    int u = leaf[p];
    mn[u] = min(mn[u], k);
    while (u >>= 1) pushup(u);
}

int query(int u, int l, int r, int L, int R) {
    if (l <= L && R <= r) return mn[u];
    int res = INF;
    if (l <= Mid) res = query(ls, l, r, L, Mid);
    if (Mid+1 <= r) res = min(res, query(rs, l, r, Mid+1, R));
    return res;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> s;
    for (int i = 1; i <= n; i++) {
        string a;
        cin >> a;
        insert(a);
    }
    build();
    dfs(0, 0);

    int u = 0, m = s.size();
    build(1, 0, m);
    modify(0, 0);
    s = ' ' + s;
    for (int i = 1; i <= m; i++) {
        int p = s[i] - 'a';
        u = tr[u][p];
        int len = mark[u];
        modify(i, query(1, max(0ll, i-len), i, 0, m) + 1);
    }

    int ans = mn[leaf[m]];
    if (ans >= INF) ans = -1;
    cout << ans << '\n';
    return 0;
}