#include using namespace std; typedef long long ll; typedef long double ld; #define rep(i, a, n) for (int i = (a); i < (n); i++) #define per(i, a, n) for (int i = (n) - 1; i >= (a); i--) struct AhoCorasick { enum {alpha = 26, first = 'a'}; struct Node { int back, next[alpha], start = -1, end = -1, nmatches = 0; Node(int v) { memset(next, v, sizeof(next)); } }; vector N; vector backp; void insert(string& s, int j) { assert(!s.empty()); int n = 0; for(auto& c : s) { int& m = N[n].next[c - first]; if (m == -1) { n = m = N.size(); N.emplace_back(-1); } else n = m; } if (N[n].end == -1) N[n].start = j; backp.push_back(N[n].end); N[n].end = j; N[n].nmatches++; } AhoCorasick(vector & pat) { N.emplace_back(-1); rep(i,0,pat.size()) insert(pat[i], i); N[0].back = N.size(); N.emplace_back(0); queue q; for (q.push(0); !q.empty(); q.pop()) { int n = q.front(), prev = N[n].back; rep(i,0,alpha) { int& ed = N[n].next[i], y = N[prev].next[i]; if (ed == -1) ed = y; else { N[ed].back = y; (N[ed].end == -1 ? N[ed].end : backp[N[ed].start]) = N[y].end; N[ed].nmatches += N[y].nmatches; q.push(ed); } } } } vector find(string word) { int n = 0; vector res; for(auto& c : word) { n = N[n].next[c - first]; res.push_back(N[n].end); } return res; } }; int main(void) { ios_base::sync_with_stdio(false); int n; cin >> n; string s; cin >> s; vector pats(n); rep(i,0,n) cin >> pats[i]; AhoCorasick ac(pats); vector is = ac.find(s); vector> slova; //cout << "x" << endl; rep(i,0,s.size()) { // cout << is[i] << endl; if (is[i] != -1) { slova.push_back({i - int(pats[is[i]].size()) + 1, i + 1}); } } slova.push_back({s.size(), s.size()+1}); sort(slova.begin(), slova.end()); int reach = 0; int best = -1; int res = 0; for(auto p : slova) { int f = p.first; int t = p.second; //cout << reach << " " << best << " " << f << " " << t << endl; if (reach >= s.size()) break; if (f > reach) { res++; if (f > reach) { reach = max(best, reach); if (f > reach) { cout << -1 << endl; return 0; } } } best = max(best, t); } cout << res << endl; }