#include #include #include #include #include #include #include #include #include #define FOR(i,a,b) for (int i = (a); i < (b); ++i) #define REP(i,n) FOR(i,0,n) #define TRACE(x) cerr << #x << " = " << x << endl #define _ << " _ " << #define pb push_back #define X first #define Y second using namespace std; typedef long long ll; typedef pair pii; const int MAX = 1<<19; const int ALPHA = 26; int V; int trie[MAX][ALPHA]; int fn[MAX]; int dulj[MAX]; int node() { REP(i, ALPHA) trie[V][i] = 0; fn[V] = 0; return V++; } int insert(char *s) { int len = (int) strlen(s); int t = 0; for (; *s; s++) { int c = *s - 'a'; if (trie[t][c] == 0) trie[t][c] = node(); t = trie[t][c]; } dulj[t] = max(dulj[t], len); return t; } void init_aho() { queue Q; Q.push(0); while (!Q.empty()) { int t = Q.front(); Q.pop(); REP(c, ALPHA) { 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]; } } } } } char veliki[MAX]; char s[MAX]; int odakle[MAX]; int main(){ ios_base::sync_with_stdio(false); { int n; scanf("%d", &n); scanf(" %s", veliki); node(); REP(i, n) { scanf(" %s", s); insert(s); } } init_aho(); REP(i, V) REP(c, ALPHA) if (trie[i][c]) dulj[trie[i][c]] = max(dulj[trie[i][c]], dulj[i]); int len = (int) strlen(veliki); int tmp_node = 0; REP(i, MAX) odakle[i] = 1<<20; REP(i, len) { int c = veliki[i] - 'a'; while(tmp_node && trie[tmp_node][c] == 0) tmp_node = fn[tmp_node]; if (trie[tmp_node][c]) tmp_node = trie[tmp_node][c]; if (dulj[tmp_node]) odakle[i] = i - dulj[tmp_node]; // TRACE(i _ odakle[i]); } for (int i=len-2; i>=0; i--) odakle[i] = min(odakle[i], odakle[i+1]); int sol = 0, pos = len-1; for (; pos>=0; ) { if (odakle[pos] >= pos) { printf("-1\n"); return 0; } sol++; pos = odakle[pos]; } printf("%d\n", sol); return 0; }