与HDU2222差不多。。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 int n,m; 9 char s[100005];10 struct Trie{11 int fail[200005],used[10005],end[200005],next[200005][130],L,root;12 int newnode(){13 for (int i=0;i<=128;i++)14 next[L][i]=-1;15 end[L++]=-1;16 return L-1;17 } 18 void clear(){19 L=0;root=newnode();20 }21 void insert(char s[],int id){22 int now=root,len=strlen(s);23 for (int i=0;i
            

Q;31 int now=root;32 for (int i=0;i<=128;i++)33 if (next[root][i]==-1) next[root][i]=root;34 else{35 fail[next[root][i]]=root;36 Q.push(next[root][i]);37 }38 while (!Q.empty()){39 int now=Q.front();40 Q.pop();41 for (int i=0;i<=128;i++){42 if (next[now][i]==-1)43 next[now][i]=next[fail[now]][i];44 else{45 fail[next[now][i]]=next[fail[now]][i];46 Q.push(next[now][i]);47 } 48 }49 } 50 }51 bool query(char s[],int n,int id){52 int len=strlen(s);53 int now=root;54 memset(used,0,sizeof used);55 bool flag=false;56 for (int i=0;i