#ifndef LOCAL #pragma GCC optimize("O3") #endif #include using namespace std; #define sim template muu & operator<<( #define ris return *this #define eni(r) sim> typename enable_if <1 r sizeof(dud(0)),muu&>::type operator<<(c g) { sim> struct rge {c b,e ;}; sim> rge range(c i, c j) {return rge{i, j};} sim> auto dud(c *r)-> decltype(cerr << *r); sim> char dud(...); struct muu { #ifdef LOCAL stringstream a; ~muu() {cerr << a.str() << endl;} eni(<) a << boolalpha << g; ris;} eni(==) ris << range(begin(g), end(g));} sim, class m mor pair r) {ris << "(" << r.first << ", " << r.second << ")";} sim mor rge u) { a << "["; for (c i = u.b; i != u.e; ++i) *this << ", " + 2 * (i == u.b) << *i; ris << "]"; } #else sim mor const c&) {ris;} #endif muu & operator()(){ris;} }; #define debug (muu() << __FUNCTION__ << "#" << __LINE__ << ": ") #define imie(r) "[" #r ": " << (r) << "] " #define imask(r) "[" #r ": " << bitset<8 * sizeof(r)>(r) << "] " #define arr(a, i) "[" #a imie(i) ": " << a[i] << "] " #define arr2(a, i, j) "[" #a imie(i) imie(j) ": " << a[i][j] << "] " using ll=long long; using vi=vector; using pii=pair; const int nax=300*1007; const int alfa=26; const int inf=1e9; int n, d; char wcz[nax]; char tmp[nax]; int m; vi graf[nax]; int syn[nax][alfa]; int dlu[nax]; int oj[nax]; int lit[nax]; int suf[nax]; int naj[nax]; int main() { scanf("%d", &n); scanf("%s", wcz+1); while(n--) { scanf("%s", tmp); int v=0; for (int i=0; tmp[i]; i++) { int c=tmp[i]-'a'; if (!syn[v][c]) { m++; graf[v].push_back(m); syn[v][c]=m; oj[m]=v; lit[m]=c; } v=syn[v][c]; } dlu[v]=strlen(tmp); } queue bfs; bfs.push(0); while(!bfs.empty()) { int v=bfs.front(); bfs.pop(); if (oj[v]) { int it=suf[oj[v]]; while(it && !syn[it][lit[v]]) it=suf[it]; if (syn[it][lit[v]]) suf[v]=syn[it][lit[v]]; dlu[v]=max(dlu[v], dlu[suf[v]]); } for (int i : graf[v]) bfs.push(i); } d=strlen(wcz+1); int v=0; for (int i=1; i<=d; i++) { int c=wcz[i]-'a'; while(v && !syn[v][c]) v=suf[v]; v=syn[v][c]; naj[i]=i-dlu[v]; } debug() << range(naj+1, naj+1+d); for (int i=d; i; i--) naj[i-1]=min(naj[i-1], naj[i]); int w=d; int wyn=0; while(w>0) { if (naj[w]==w) { wyn=-1; break; } wyn++; w=naj[w]; } printf("%d\n", wyn); return 0; }