#include<bits/stdc++.h> using namespace std; queue<int> q; const int N = 500010; struct AC_automaton { int c[N][26], val[N], fail[N], cnt; //c数组记录字典树节点,val数组为该节点是否为字符串结尾(个数)(记录字符串结束的位置), fail记录失配指针, cnt记录节点标号(对应val) //cnt作用:模拟动态开点 void ins(char *s)//向字典树中插入字符串,s为模式串 { int len = strlen(s); int now = 0;//从根节点0开始 for(int i = 0; i < len; i++) { int v = s[i] - 'a';//获取当前字符的值 if(!c[now][v])c[now][v] = ++cnt;//如果这个节点没开,则开点 now = c[now][v];//now移动到新节点,开始匹配下一个 } val[now]++;//字符串插入完毕后在尾部打标记,val[u]表示以该点结尾的字符串个数 } void build()//获取每个节点的失配指针 { for(int i = 0; i < 26; i++) if(c[0][i])fail[c[0][i]] = 0, q.push(c[0][i]);//首先将与根节点相连的点入队,即首字母入队,并赋失配指针为0 while(!q.empty()) { int u = q.front(); q.pop();//出队 for(int i = 0; i < 26; i++) { if(c[u][i])fail[c[u][i]] = c[fail[u]][i], q.push(c[u][i]);//如果该节点存在,则他的失配指针为它的上一个失配指针处的失配指针,并入队 else c[u][i] = c[fail[u]][i];//该点不存在只更新fail指针 } } } int query(char *s)//查询文本串中模式串的个数,s为文本串 { int len = strlen(s); int now = 0, ans = 0;//ans记录答案(模式串个数), 从根节点开始 for(int i = 0; i < len; i++) { now = c[now][s[i] - 'a'];//从当前节点向下走 for(int t = now; t && ~val[t]; t = fail[t])ans += val[t], val[t] = -1;//遍历该节点前失配指针,并统计个数,清楚val(避免重复统计) } return ans; } }AC; int n; char p[1000005]; int main() { scanf("%d", &n); for(int i = 1; i <= n; i++)scanf("%s", p), AC.ins(p); AC.build(); scanf("%s", p); int ans = AC.query(p); printf("%d\n", ans); return 0; }