#include #include #include #include using namespace std; typedef long long llint; typedef pair pii; const int MAX = 3 * (1 << 17); const int ALPHA = 26; int V; int trie[MAX][ALPHA]; int fn[MAX]; int sn[MAX]; int length[MAX]; int node() { for (int i = 0; i < ALPHA; ++i) trie[V][i] = 0; fn[V] = 0; sn[V] = 0; length[V] = 0; return V++; } int insert(char *s) { int t = 0; int len = 0; for (; *s; ++s) { int c = *s - 'a'; if (trie[t][c] == 0) trie[t][c] = node(); t = trie[t][c]; ++len; } length[t] = len; return t; } void init_aho() { queue Q; Q.push(0); while (!Q.empty()) { int t = Q.front(); Q.pop(); for (int c = 0; c < ALPHA; ++c) { int x = trie[t][c]; if (x) { Q.push(x); if (t) { fn[x] = fn[t]; while (fn[x] && trie[fn[x]][c] == 0) fn[x] = fn[fn[x]]; if (trie[fn[x]][c]) fn[x] = trie[fn[x]][c]; if (length[fn[x]]) { sn[x] = fn[x]; } else { sn[x] = sn[fn[x]]; } } } } } } int l; char word[MAX]; char buff[MAX]; int sol[MAX]; void init_sol() { int t = 0; memset(sol, -1, sizeof sol); for (int i = 0; word[i]; ++i) { int c = word[i] - 'a'; while (t && trie[t][c] == 0) t = fn[t]; if (trie[t][c]) { t = trie[t][c]; int last = t; while (last) { if (length[last]) { sol[i - length[last] + 1] = max(sol[i - length[last] + 1], i); } last = sn[last]; } } } } int solve() { for (int i = 1; word[i]; ++i) { sol[i] = max(sol[i-1], sol[i]); } int last = 0; int ans = 0; while (word[last+1]) { ++ans; int next = sol[last+1]; if (next <= last) return -1; last = next; } return ans; } int main(void) { scanf("%d", &l); scanf("%s", word); for (int i = 0; i < l; ++i) { scanf("%s", buff); insert(buff); } init_aho(); init_sol(); printf("%d\n", solve()); return 0; }