当然可以在SA上二分答案，但看起来会被卡log。考虑对模板串建出AC自动机，用母串在上面跑，标记上所有能到达的点。注意到达某个点时需要标记所有其通过fail指针可以走到的点，如果遇到一个标记过的点就可以退出，因为显然后面所指向的已被标记。查询时由每个模板串的结尾节点向上暴力找第一个被标记的点即可。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> #include<vector> using namespace std; int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define N 10000010 int n,m,trie[N][4],fail[N],q[N],deep[N],fa[N],p[N],id[100],cnt=0; bool flag[N]; char s[N],s2[110]; void ins(char *a,int v) { int n=strlen(a+1),k=0; for (int i=1;i<=n;i++) { if (!trie[k][id[a[i]]]) trie[k][id[a[i]]]=++cnt,deep[cnt]=deep[k]+1,fa[cnt]=k; k=trie[k][id[a[i]]]; } p[v]=k; } void build() { int head=0,tail=0;for (int i=0;i<4;i++) if (trie[0][i]) q[++tail]=trie[0][i]; do { int x=q[++head]; for (int i=0;i<4;i++) if (trie[x][i]) q[++tail]=trie[x][i],fail[trie[x][i]]=trie[fail[x]][i]; else trie[x][i]=trie[fail[x]][i]; }while (head<tail); } int main() { #ifndef ONLINE_JUDGE freopen("bzoj4327.in","r",stdin); freopen("bzoj4327.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif n=read(),m=read(); scanf("%s",s+1);id['E']=0,id['S']=1,id['W']=2,id['N']=3; for (int i=1;i<=m;i++) { scanf("%s",s2+1); ins(s2,i); } build(); int k=0;flag[0]=1; for (int i=1;i<=n;i++) { k=trie[k][id[s[i]]]; flag[k]=1; int x=k;while (!flag[fail[x]]) x=fail[x],flag[x]=1; } for (int i=1;i<=m;i++) { int x=p[i]; while (!flag[x]) x=fa[x]; printf("%d ",deep[x]); } return 0; }