有多个case, 每个case第一行是一个正整数N,之后N行每行一个string,代表string库, 每个string由a-z 26个小写字母组成,然后是一个正整数M,之后M行每行一个string代表你所要询问的string。
每个case输出M行,每行一个正整数,代表当前询问的string是库中多少个string的子串
3 aaa aaa baa 2 aa ba 1 a 1 a
3 1 1
//使用kmp算法暴力求解 #include <bits/stdc++.h> using namespace std; void Next(const string &key, vector<int> &next) { next[0] = -1; int i = 0, j = -1; while (i != key.size()-1) { if (j == -1 || key[i] == key[j]) { next[++i] = ++j; } else { j = next[j]; } } } int KMP(const string &word, const string &key) { vector<int> next(key.size(), 0); Next(key, next); int i = 0, j = 0; while (i != word.size() && j != key.size()) { if (j == -1 || word[i] == key[j]) { ++i; ++j; } else { j = next[j]; } } return j == key.size() ? i - j : -1; } void CountPreix(const vector<string> &words, const vector<string> &keys, vector<int> &counts) { for (int i = 0; i < keys.size(); ++i) { for (int j = 0; j < words.size(); ++j) { if (KMP(words[j], keys[i]) != -1) { counts[i]++; } } } } int main() { int n = 0; while (cin >> n) { vector<string> words(n); for (int i = 0; i < n; ++i) { cin >> words[i]; } int m = 0; cin >> m; vector<string> keys(m); for (int i = 0; i < m; ++i) { cin >> keys[i]; } vector<int> counts(m, 0); CountPreix(words, keys, counts); for (int count : counts) { cout << count << endl; } } return 0; }