#define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; class AhoCorasick { private: int n; vector > next; vector > match; vector failure; public: AhoCorasick(const vector& pattern){ next.assign(1, vector(128, -1)); match.assign(1, vector()); for(unsigned i=0; i(128, -1)); match.push_back(vector()); } curr = next[curr][pattern[i][j]]; } match[curr].push_back(i); } n = next.size(); failure.resize(n, 0); vector node1(1, 0); while(!node1.empty()){ vector node2; for(unsigned i=0; i& checkMatch(int curr){ return match[curr]; } }; int main() { string s; int m; cin >> s >> m; int n = s.size(); vector c(m); for(int i=0; i> c[i]; AhoCorasick ac(c); int k = 0; int ans = 0; for(int i=0; i