对于100%的数据，N<=10^7，M<=10^5，每一段文字的长度<=100。
Solution：
本题AC自动机+简单搜索就好了。
存下主串，再对所有模式串构建AC自动机（记录下每个串结尾的节点和每个节点的前趋以及深度），然后直接在trie树中查询主串，对于扫到的节点p，标记所有没访问过的fail[p]节点（访问过的就不用再往上标记了），然后直接从每个模式串的尾节点往上dfs，搜到的第一个被标记的节点的深度就是答案了。
代码：
1 #include<bits/stdc++.h> 2 #define il inline 3 #define ll long long 4 #define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++) 5 #define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--) 6 using namespace std; 7 const int N=1000005; 8 int n,m,trie[N][4],cnt,ed[N],fail[N],dep[N],pre[N]; 9 char t[N*10],s[N]; 10 bool vis[N]; 11 12 il int id(char c){ 13 if(c==‘E‘)return 0; 14 if(c==‘S‘)return 1; 15 if(c==‘W‘)return 2; 16 return 3; 17 } 18 19 il void insert(char *s,int num){ 20 int len=strlen(s),p=0,x; 21 For(i,0,len-1){ 22 x=id(s[i]); 23 if(!trie[p][x])dep[++cnt]=dep[p]+1,trie[p][x]=cnt,pre[cnt]=p; 24 p=trie[p][x]; 25 } 26 ed[num]=p; 27 } 28 29 il void bfs(){ 30 queue<int>q; 31 For(i,0,3)if(trie[0][i])q.push(trie[0][i]); 32 while(!q.empty()){ 33 int u=q.front();q.pop(); 34 For(i,0,3) { 35 int v=trie[u][i]; 36 if(v) fail[v]=trie[fail[u]][i],q.push(v); 37 else trie[u][i]=trie[fail[u]][i]; 38 } 39 } 40 } 41 42 il int dfs(int now){ 43 if(vis[now])return dep[now]; 44 if(!now) return 0; 45 dfs(pre[now]); 46 } 47 48 il void search(char *s){ 49 int len=strlen(s),p=0; 50 For(i,0,len-1){ 51 p=trie[p][id(s[i])]; 52 for(int j=p;j&&!vis[j];j=fail[j]) vis[j]=1; 53 } 54 For(i,1,m) printf("%d\n",dfs(ed[i])); 55 } 56 57 int main(){ 58 scanf("%d%d%s",&n,&m,t); 59 For(i,1,m) scanf("%s",s),insert(s,i); 60 bfs(); 61 search(t); 62 return 0; 63 }
原文：https://www.cnblogs.com/five20/p/9471126.html