AC自动机模板...
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <iostream>
#include <sstream>#define ll long longusing namespace std;struct AcAutoMachine {
#define N 500005 // 字典的节点数，比最大数据略大即可
#define M 26 // 字典的字母数，此为精确值int next[N][M], fail[N], data[N], size;int queu[N], head, tail;int code(const char &c) { // 将字符哈希成结点标号return c - 'a';}void clear(int x) {memset(next[x], -1, sizeof(next[x]));fail[x] = -1; data[x] = 0;}void init() {clear(0);size = 1;}void insert(char *str) {int p = 0, idx;while (*str) {idx = code(*str);if (next[p][idx] == -1) {clear(size);next[p][idx] = size++;}p = next[p][idx];str++;}data[p]++;}void buildac() {int p, pp, fp, fpp;head = tail = 0;queu[tail++] = 0;while (head < tail) {p = queu[head++];for (int i = 0; i < M; i++) {if ((pp = next[p][i]) != -1) {for (fp = fail[p]; fp != -1; fp = fail[fp]) {if ((fpp = next[fp][i]) != -1) {fail[pp] = fpp;// 将fail链上后继结点的权值加到前驱结点中，// 这样计算权值时就不需要遍历fail链，看情况是否需要。// data[pp] += data[fpp];break;}}if (fp == -1) fail[pp] = 0;queu[tail++] = pp;} else { // 重构next，看题目是否需要if (p == 0) next[p][i] = 0;else next[p][i] = next[fail[p]][i];}}}}int query(char *str) {int p = 0, ret = 0, idx, pp;while (*str) {idx = code(*str);p = next[p][idx];for (pp = p; pp != -1 && data[pp] != -1; pp = fail[pp]) {ret += data[pp];data[pp] = -1;}++str;}return ret;}
} A;char str[1000005];int main() {int n, i, t;for (scanf("%d", &t); t--; ) {scanf("%d", &n);A.init();for (i = 0; i < n; i++) {scanf("%s", str);A.insert(str);}A.buildac();scanf("%s", str);printf("%d\n", A.query(str));}return 0;
}