#include using namespace std; const int maxn = 300005; int sa[maxn], sapos[maxn], rmq[2 * maxn]; void suffarray(string str) { int n = str.size(); //cout << str << ' ' << n << endl; vector p(n), q(n); for (int i = 0; i < n; ++i) { p[i] = str[i], sa[i] = i; } for (int off = 1; off < n; off *= 2) { auto cmp = [&] (int a, int b) { if (p[a] != p[b]) return p[a] < p[b]; if (a + off >= n || b + off >= n) return a > b; return p[a + off] < p[b + off]; }; sort(sa, sa + n, cmp); q[sa[0]] = 0; for (int i = 1; i < n; ++i) { q[sa[i]] = q[sa[i - 1]]; if (cmp(sa[i - 1], sa[i])) q[sa[i]]++; } swap(p, q); } for (int i = 0; i < n; ++i) { sapos[sa[i]] = i; } } int main() { ios::sync_with_stdio(0), cin.tie(0); int n; cin >> n; string str; cin >> str; suffarray(str); int N = str.size(); //for (int i = 0; i < N; ++i) //cout << sapos[i] << ' ' << str.substr(sa[i]) << endl; for (int i = 0; i < n; ++i) { string s; cin >> s; int lor = 0, hir = N; for (int i = 0; s[i]; ++i) { int lo = lor, hi = hir; while (lo < hi) { int md = (lo + hi) / 2; if (str[sa[md] + i] < s[i]) { lo = md + 1; } else { hi = md; } } lor = lo, hi = hir; while (lo < hi) { int md = (lo + hi) / 2; if (str[sa[md] + i] <= s[i]) { lo = md + 1; } else { hi = md; } } hir = lo; } //cout << lor << ' ' << hir << endl; for (int l = lor + N, r = hir + N; l < r; l /= 2, r /= 2) { if (l & 1) rmq[l] = max(rmq[l], (int) s.size()), l++; if (r & 1) r--, rmq[r] = max(rmq[r], (int) s.size()); } } int sol = 0, l = 0, mx = 0; for (int i = 0; i < N;) { while (l <= i) { int len = 0; for (int p = sapos[l] + N; p; p /= 2) len = max(len, rmq[p]); //cout << l << ' ' << len << endl; mx = max(mx, l + len); l++; } if (mx <= i) { cout << -1; return 0; } i = mx; mx = 0; sol++; } cout << sol; }