#include using namespace std; typedef long long ll; const int ALPHABET_SIZE = 26; int to_index(char c) { return c - 'a'; } struct trie { struct __trieNode { vector endsHere; __trieNode *nextOutput, *son[ALPHABET_SIZE], *higher; __trieNode() { nextOutput = higher = NULL; memset(son, 0, sizeof(son)); } }; __trieNode *root; int __size; trie() { root = NULL; __size = 0; } void insert(const string &s) { if (!root) root = new __trieNode(); __trieNode *kde = root; for (int i = 0;i < s.size(); i++) { int idx = to_index(s[i]); if (!kde->son[idx])kde->son[idx] = new __trieNode(); kde = kde->son[idx]; } kde->endsHere.push_back(__size++); } int find(const string &s) { __trieNode *kde = root; for (int i = 0;ison[to_index(s[i])]; } if (!kde || kde->endsHere.empty()) return -1; return kde->endsHere[0]; } void create_automaton() { if(!root) return; queue<__trieNode *> q; q.push(root); __trieNode *superRoot = new __trieNode(); for(int i = 0;ison[i] = root; root->higher = superRoot; while(!q.empty()) { __trieNode *kde = q.front(); q.pop(); for(int i = 0;ison[i]) { __trieNode *cand = kde->higher; while(!cand->son[i]) cand = cand->higher; kde->son[i]->higher = cand->son[i]; if(kde->son[i]->higher->endsHere.empty()) kde->son[i]->nextOutput = kde->son[i]->higher->nextOutput; else kde->son[i]->nextOutput = kde->son[i]->higher; q.push(kde->son[i]); } } } } // kde konci a co set > report_matched_words(const string &s) { set > result; __trieNode *kde = root; for(int i = 0;ison[idx]) kde = kde->higher; kde = kde->son[idx]; __trieNode *out = kde; while(out) { //result.insert(out->endsHere.begin(), out->endsHere.end()); for(auto x: out->endsHere){ result.insert({i, x}); } out = out->nextOutput; } } return result; } }; int main() { trie t; int n; cin >> n; string wanted; vector words(n); cin >> wanted; for(int i = 0; i < n; i++){ cin >> words[i]; t.insert(words[i]); } t.create_automaton(); int m = wanted.length(); vector finishes(m,0); for(auto x: t.report_matched_words(wanted)){ int startIndex = x.first - words[x.second].length() + 1; finishes[startIndex] = max(finishes[startIndex], x.first); // cout << "kde konci = " << x.first << " co konci = " << x.second << " start index = " << startIndex << endl; } // cout << "finishes: "; for(auto x: finishes) cout << x << " "; cout << endl; int nextFinish = -1; int nextFinishCandidate = finishes[0]; int res = 0; for(int i = 0; i < m; i++){ nextFinishCandidate = max(nextFinishCandidate, finishes[i]); if(nextFinish < i){ nextFinish = nextFinishCandidate; res++; } } cout << res << endl; return 0; }