\(SAM\)板子，直接建出\(SAM\)之后把每个串放上去匹配就好了
代码
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define maxn 10000005#define re register#define LL long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))char S[maxn];int n,m,cnt=1,lst=1;int fa[maxn<<1],son[maxn<<1][4],len[maxn<<1];inline void ins(int c){ ???int f=lst,p=++cnt; lst=p; ???len[p]=len[f]+1; ???while(f&&!son[f][c]) son[f][c]=p,f=fa[f]; ???if(!f) {fa[p]=1;return;} ???int x=son[f][c]; ???if(len[f]+1==len[x]) {fa[p]=x;return;} ???int y=++cnt; ???len[y]=len[f]+1,fa[y]=fa[x],fa[x]=fa[p]=y; ???for(re int i=0;i<4;i++) son[y][i]=son[x][i]; ???while(f&&son[f][c]==x) son[f][c]=y,f=fa[f];}int main(){ ???scanf("%d%d",&n,&m);scanf("%s",S+1); ???for(re int i=1;i<=n;i++) ????{ ???????if(S[i]==‘N‘) S[i]=1; ???????if(S[i]==‘E‘) S[i]=2; ???????if(S[i]==‘S‘) S[i]=3; ???????if(S[i]==‘W‘) S[i]=0; ???} ???for(re int i=1;i<=n;i++) ins(S[i]); ???while(m--) ???{ ???????scanf("%s",S+1); ???????int len=strlen(S+1); ???????int now=1,L=0; ???????for(re int i=1;i<=len;i++) ????????{ ???????????if(S[i]==‘N‘) S[i]=1; ???????????if(S[i]==‘E‘) S[i]=2; ???????????if(S[i]==‘S‘) S[i]=3; ???????????if(S[i]==‘W‘) S[i]=0; ???????} ???????for(re int i=1;i<=len;i++) ???????if(son[now][S[i]]) L++,now=son[now][S[i]];else break; ???????printf("%d\n",L); ???} ???return 0;}bzoj 4327:JSOI2012 玄武密码
原文地址：https://www.cnblogs.com/asuldb/p/10225465.html