#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e7 + 5;
const int MAX = 10000000;
int cnt;
struct node{
node *next[26];
node *fail;
int sum;
};
node *root;
char key[70];
node *q[MAX];
int head,tail;
node *newnode;
char pattern[maxn];
int N;
void Insert(char s[]) //建trie树
{
node *p = root;
for(int i = 0; s[i]; i++) //注意中间的东西，s[i]不为空时。
{
int x = s[i] - 'a';
if(p->next[x] == NULL)
{
newnode = new node; //先用newnode指针把地址建好，然后在31行直接传到p->next[x]
for(int j=0;j<26;j++)
newnode->next[j] = NULL;
newnode->sum = 0; //记录是几个单词的结尾
newnode->fail = NULL;
p->next[x] = newnode;
}
p = p->next[x];
}
p->sum++;
}
void build_fail_pointer()
{
head = 0;
tail = 1;
q[head] = root; //手动模拟队列
node *p;
node *temp;
while(head < tail)
{
temp = q[head++];
for(int i = 0; i <= 25; i++)
{
if(temp->next[i] != NULL)
{
if(temp == root) //root的fail指针为自己
{
temp->next[i]->fail = root;
}
else
{
p = temp->fail; //将父节点的fail传给儿子
while(p != NULL)
{
if(p->next[i] != NULL)
{
temp->next[i]->fail = p->next[i];
break;
}
p = p->fail;
}
if(p == NULL) temp->next[i]->fail = root;//如果失败，fail就为根节点
}
q[tail++] = temp->next[i];
}
}
}
}
void ac_automation(char ch[])
{
node *p = root;
int len = strlen(ch);
for(int i = 0; i < len; i++) //主文本搜索到哪了
{
int x = ch[i] - 'a';
while(p->next[x] == NULL&& p != root) p = p->fail; //如果失败就从fail开始再找
p = p->next[x];
if(p == NULL) p = root; //判断是否找到了
node *temp = p;
while(temp != root)
{
if(temp->sum >= 0) //如果没加过，就加
{
cnt += temp->sum;
temp->sum = -1;
}
else break; //加过就不加了
temp = temp->fail; //把相同后缀的单词都加上
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
root=new node;
for(int j=0;j<26;j++) root->next[j] = NULL;
root->fail = 0;
root->sum = 0;
scanf("%d",&N);
getchar();
for(int i = 1; i <= N; i++)
{
gets(key);
Insert(key);
}
gets(pattern);
cnt = 0;
build_fail_pointer();
ac_automation(pattern);
printf("%d
",cnt);
}
return 0;
}
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<queue> using namespace std; #define duke(i,a,n) for(int i = a;i <= n;i++) #define lv(i,a,n) for(int i = a;i >= n;i--) #define clean(a) memset(a,0,sizeof(a)) const int INF = 1 << 30; const int mod = 998244353; typedef double db; template <class T> void read(T &x) { char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') {x = x * 10 + c - '0';if(x > mod) x %= mod;} if(op) x = -x; } template <class T> void write(T x) { if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar('0' + x % 10); } const int maxn = 1e6 + 5; char s[maxn]; int ch[maxn][30],cnt = 0,val[maxn],f[maxn],n; int getnum(char c) { return c - 'a'; } void insert(char *s) { int m = strlen(s); int now = 0; duke(i,0,m - 1) { int c = getnum(s[i]); if(!ch[now][c]) ch[now][c] = ++cnt; now = ch[now][c]; } val[now]++; } void build() { queue <int> q; duke(i,0,25) { if(ch[0][i]) q.push(ch[0][i]); } while(!q.empty()) { int now = q.front(); q.pop(); duke(i,0,25) { if(ch[now][i]) f[ch[now][i]] = ch[f[now]][i],q.push(ch[now][i]); else ch[now][i] = ch[f[now]][i]; } } } int query(char *s) { int len = strlen(s),now = 0,ans = 0; duke(i,0,len - 1) { int c = getnum(s[i]); now = ch[now][c]; for(int j = now;j && val[j] != -1;j = f[j]) ans += val[j],val[j] = -1; } return ans; } int main() { read(n); duke(i,1,n) { scanf("%s",s); insert(s); } build(); scanf("%s",s); printf("%d ",query(s)); return 0; }