题目

对于每一段文字 tt，求出其最长的前缀 pp，满足 pp 是 ss 的子串，其中ss是字串。

题解

我们可以用ac自动机来做，先把所有字串建个ac自动机，然后用母串在上面跑，把那些点都进行标记，最后dfs一次就好

code

#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
using namespace std;
const int N=1e7+5;
const int M=1e6+5;//
char s[N],tt[105];
int ch[M][4],cnt,b[M],ch1[M][4],n,m,c,h,t,now,l,tot,val[N],r,u,v,f[N],last[N];
int sum[M];
int q[M],ans[M];
int G(char x){
	if (x=='E') return 0;
	if (x=='S') return 1;
	if (x=='W') return 2;
	if (x=='N') return 3;
}
void ins(int x){
	now=0;  
	fo(i,1,l){
		c=G(tt[i]);
		if (!ch[now][c]) ch[now][c]=++tot;
		ch1[now][c]=ch[now][c];
		
		now=ch[now][c];
	}
	b[x]=now;
}
void build(){
	h=t=0;
	fo(i,0,3) if (ch[0][i]) q[++t]=ch[0][i];
	while (h<t){
		r=q[++h];
		fo(i,0,3){
			u=ch[r][i];
			if (!u){
				ch[r][i]=ch[f[r]][i]; continue;
			}
			v=f[r];
			while (v && !ch[v][i]) v=f[v];
			f[u]=ch[v][i];
//			last[u]=val[f[u]] ? f[u]:last[f[u]];
			q[++t]=u;
		}
	}
}
void match(){
	now=0;
	fo(i,1,n){
		c=G(s[i]);
		u=ch[now][c];
		sum[u]++;
		while (f[u]) {
			sum[f[u]]++;
			u=f[u];
		}
		now=ch[now][c];
	}
}
void dfs(int x,int d,int z){
	if (sum[x]) ans[x]=d;
	else ans[x]=z;
	fo(i,0,3){
		if (ch1[x][i]) {
			if (sum[x]) dfs(ch1[x][i],d+1,d);
			else dfs(ch1[x][i],d+1,z);
		}
	}	 
}
int main(){
//	freopen("data.in","r",stdin);
	scanf("%d %d",&n,&m);
	scanf("%s",s+1);
	fo(i,1,m) {
		scanf("%s",tt+1);
		l=strlen(tt+1);
		ins(i);
	}
	
	build();
	match();
	
	dfs(0,0,0);
	fo(i,1,m) {
		printf("%d\n",ans[b[i]]);
	}
	return 0;
}