想看加强版的戳这里（施工ing，作者正努力中）~
先贴题目吧哎~
题目： （数据范围困了我好久 TAT）
反正涉及字符串的算法都很玄学，此模板不例外，能用到此模板的都至少 省选+ 了。
所需知识点：KMP、Trie。
由于本人比较无能，忘了以前怎么理解的（包括 KMP 和 Trie），完全忘了，只找到模板，只会套用，等我理解了再来补坑吧！！~
实在要看思路的这里有传送门：
只贴标程（以后再补，一个模板贼长了）：
1 type 2 node=record 3 sum,failed:longint; 4 son:array ['a'..'z'] of longint; 5 end; 6 var 7 t:array [0..1000001] of node; 8 d,v:array[0..1000001] of longint; 9 s:array[0..1000001] of char; 10 n,len,tot,ans,i:longint; 11 procedure insert; 12 var 13 root,i:longint; 14 begin 15 root:=0; 16 for i:=1 to len do 17 begin 18 if t[root].son[s[i]]=0 then 19 begin 20 inc(tot); 21 t[tot].failed:=-1; 22 t[root].son[s[i]]:=tot; 23 end; 24 root:=t[root].son[s[i]]; 25 end; 26 inc(t[root].sum); 27 end; 28 procedure bfs; 29 var 30 h,r,now,s,f:longint; 31 ch:char; 32 begin 33 h:=1; 34 r:=2; 35 while h0 then 42 begin 43 f:=t[now].failed; 44 while (f<>-1) and (t[f].son[ch]=0) do 45 f:=t[f].failed; 46 if f=-1 then t[s].failed:=0 47 else t[s].failed:=t[f].son[ch]; 48 d[r]:=s; 49 inc(r); 50 end; 51 end; 52 inc(h); 53 end; 54 end; 55 procedure AC_Automaton; 56 var 57 i,now,k,x:longint; 58 begin 59 i:=1; 60 now:=0; 61 while i<=len do 62 begin 63 k:=t[now].son[s[i]]; 64 if k<>0 then 65 begin 66 x:=k; 67 while (v[x]=0) and (x<>0) do 68 begin 69 v[x]:=1; 70 inc(ans,t[x].sum); 71 x:=t[x].failed; 72 end; 73 now:=k; 74 inc(i); 75 end else 76 begin 77 x:=now; 78 while (x<>-1) and (t[x].son[s[i]]=0) do 79 x:=t[x].failed; 80 now:=x; 81 if now=-1 then 82 begin 83 now:=0; 84 inc(i); 85 end; 86 end; 87 end; 88 end; 89 begin 90 readln(n); 91 t[0].failed:=-1; 92 for i:=1 to n do 93 begin 94 len:=0; 95 while not eoln do 96 begin 97 inc(len); 98 read(s[len]); 99 if not (s[len] in ['a'..'z']) then100 begin101 dec(len);102 break;103 end;104 end;105 readln;106 insert;107 end;108 bfs;109 len:=0;110 while not eoln do111 begin112 inc(len);113 read(s[len]);114 if not (s[len] in ['a'..'z']) then115 begin116 dec(len);117 break;118 end;119 end;120 readln;121 AC_Automaton;122 writeln(ans);123 end.