1 #include "bits/stdc++.h"
2 using namespace std;
3 typedef long long LL;
4 const int MAX1=1e6+5,MAX2=5e5+5;
5 int n;char s[MAX1];
6 struct Aho{
7 struct state{
8 int next[27];
9 int fail,cnt;
10 }sst[MAX1];
11
12 int size;
13 queue <int> q;
14
15 void init(){
16 int i,j;
17 while (!q.empty()) q.pop();
18 for (i=0;i<MAX2;i++){
19 memset(sst[i].next,0,sizeof(sst[i].next));
20 sst[i].fail=sst[i].cnt=0;
21 }
22 size=0;
23 }
24
25 void insert(char *s){
26 int i,j,ls=strlen(s);
27 int now=0;char c;
28 for (i=0;i<ls;i++){
29 c=s[i];
30 if (!sst[now].next[c-'a']) sst[now].next[c-'a']=++size;
31 now=sst[now].next[c-'a'];
32 }
33 sst[now].cnt++;
34 }
35
36 void build(){
37 int i,j;
38 q.push(0);sst[0].fail=-1;
39 while (!q.empty()){
40 int u=q.front();q.pop();
41 for (i=0;i<26;i++)
42 if (sst[u].next[i]){
43 if (u==0) sst[sst[u].next[i]].fail=0;
44 else{
45 int v=sst[u].fail;
46 while (v!=-1){
47 if (sst[v].next[i]){
48 sst[sst[u].next[i]].fail=sst[v].next[i];
49 break;
50 }
51 v=sst[v].fail;
52 }
53 if (v==-1) sst[sst[u].next[i]].fail=0;
54 }
55 q.push(sst[u].next[i]);
56 }
57 }
58 }
59
60 int get(int u){
61 int an=0;
62 while (u){
63 an+=sst[u].cnt;
64 sst[u].cnt=0;
65 u=sst[u].fail;
66 }
67 return an;
68 }
69
70 int match(char *s){
71 int i,j,ls=strlen(s);
72 int now=0,cnt=0;
73 for (i=0;i<ls;i++){
74 char c=s[i];
75 if (sst[now].next[c-'a']) now=sst[now].next[c-'a'];
76 else{
77 int p=sst[now].fail;
78 while (p!=-1 && sst[p].next[c-'a']==0) p=sst[p].fail;
79 if (p==-1) now=0;
80 else now=sst[p].next[c-'a'];
81 }
82 if (sst[now].cnt)
83 cnt+=get(now);
84 }
85 return cnt;
86 }
87 }aho;
88 int main(){
89 freopen ("aho.in","r",stdin);freopen ("aho.out","w",stdout);
90 int i,j;
91 aho.init();
92 scanf("%d\n",&n);
93 for (i=1;i<=n;i++){
94 scanf("%s",s);
95 aho.insert(s);
96 }
97 aho.build();
98 scanf("%s",s);
99 printf("%d",aho.match(s));
100 return 0;
101