制作失配函数时注意两点：

一是从上往下计算，开个队列~

二是采用大白书的“一视同仁”法提高效率，就是一条边走不下去时直接把这条边接在失配函数的对应边上。

废话少说上代码~

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 //#include
           
             7 using namespace std; 8 9 #define maxt 1000011 10 #define maxs 500011 11 #define maxc 26 12 int n; 13 char s[maxs],T[maxt];int Case; 14 struct Trie 15 { 16 int size,ch[maxs][maxc],fail[maxs],last[maxs],val[maxs],ans;bool vis[maxs]; 17 void clear() 18 { 19 memset(ch[0],0,sizeof(ch[0])); 20 memset(vis,0,sizeof(vis)); 21 val[0]=0;size=0;ans=0; 22 } 23 int idx(char c) { return c-'a';} 24 void insert(char* s) 25 { 26 int now=0,ls=strlen(s); 27 for (int i=0;i