注意有相同模式串出现的可能， 且每个串最多记一次答案
code:
#include <iostream> #include <cstdio> #include <cstring> #include <string> using namespace std; #define clr(a) memset(a, 0, sizeof a) const int N = 10010 * 50; struct AC_Auto{ int ch[N][26], f[N], v[N], last[N], sz, q[N]; void init(){ clr(ch); clr(f); clr(v); clr(q); clr(last); /**clr(vis);*/ sz = 1; } void insert(string s){ int len = s.length(); int u = 0; for(int i = 0; i < len; ++i){ int c = s[i] - 'a'; if(!ch[u][c]) ch[u][c] = sz++; u = ch[u][c]; } ++v[u]; last[u] = 1; } void getFail(){ q[0] = 0; int now = 0, top = 1; while(now < top){ int t = q[now++]; for(int i = 0; i < 26; ++i){ if(ch[t][i]){ int p = ch[t][i], u = f[t]; while(!ch[u][i] && u) u = f[u]; f[p] = t == 0 ? 0 : ch[u][i]; last[p] |= last[f[p]]; /**v[p] = v[p] || v[f[p]];*/ q[top++] = p; } else ch[t][i] = ch[f[t]][i]; } } } int dfs(int x){ if(!last[x]) return 0; //vis[x] = 1; int ret = 0; ret += v[x] + dfs(f[x]); v[x] = 0;/**记过答案清掉标记1*/ return ret; } int cal(string s){ int u = 0, ans = 0; for(int i = 0; i < s.length(); ++i){ u = ch[u][s[i] - 'a']; if(last[u]) ans += dfs(u); } return ans; } }ac; int main(){ //freopen("in.txt", "r", stdin); int t, n; string s; cin >> t; while(t--){ ac.init(); cin >> n; for(int i = 0; i < n; ++i){ cin >> s; ac.insert(s); } ac.getFail(); cin >> s; cout << ac.cal(s) << endl; } return 0; }