[文章目录]
Description
对于每一段文字，其前缀在母串上的最大匹配长度是多少呢？母串长度<=10^7，文字段数<=10^5，每段长度<=100
AC自动机。将每段文字建一个AC自动机，将母串进行匹配，标记匹配到的节点，通过fail上传标记，目的是使得所有的被匹配节点被标记。（然而失智的我写的下传。。。），每个节点被标记的父辈节点中深度最大的节点深度即为当前节点到根的串的最长匹配前缀长度。
深度的话，可以直接在建树的时候就求出来，还方便以后判断当前节点是否是真儿子，还是trie图造出来的。
块状链表一样的代码。。。233
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,tot=1;
inline int ch(const char x)
{
if(x=='E') return 0; if(x=='W') return 1;
if(x=='S') return 2; if(x=='N') return 3;
}
struct trie {
int c[4],fail,ans,dep,dan;
}tr[10001000];
int ques[101000],q[1001000];
char s[10001000],t[110];
void dfs(int x)
{
if(!x) return ;
printf("now in %d: danger=%d\n",x,tr[x].dan);
for(int i=0;i!=4;++i)
if(tr[tr[x].c[i]].dep==tr[x].dep+1)
printf("goto%d\n",i),dfs(tr[x].c[i]),puts("out");
}
int main()
{
scanf("%d%d",&n,&m);
scanf("%s",s); int len,p;
for(int i=1;i<=m;++i)
{
scanf("%s",t);
len=strlen(t); p=1;
for(int j=0;j!=len;++j)
{
if(!tr[p].c[ch(t[j])]) tr[p].c[ch(t[j])]=++tot;
p=tr[p].c[ch(t[j])]; tr[p].dep=j+1;
}
ques[i]=p;
}
int l=1,r=0;
if(tr[1].c[0]) tr[tr[1].c[0]].fail=1,q[++r]=tr[1].c[0]; else tr[1].c[0]=1;
if(tr[1].c[1]) tr[tr[1].c[1]].fail=1,q[++r]=tr[1].c[1]; else tr[1].c[1]=1;
if(tr[1].c[2]) tr[tr[1].c[2]].fail=1,q[++r]=tr[1].c[2]; else tr[1].c[2]=1;
if(tr[1].c[3]) tr[tr[1].c[3]].fail=1,q[++r]=tr[1].c[3]; else tr[1].c[3]=1;
while(l<=r)
{
p=q[l++];
if(tr[p].c[0]) tr[tr[p].c[0]].fail=tr[tr[p].fail].c[0],q[++r]=tr[p].c[0];
else tr[p].c[0]=tr[tr[p].fail].c[0];
if(tr[p].c[1]) tr[tr[p].c[1]].fail=tr[tr[p].fail].c[1],q[++r]=tr[p].c[1];
else tr[p].c[1]=tr[tr[p].fail].c[1];
if(tr[p].c[2]) tr[tr[p].c[2]].fail=tr[tr[p].fail].c[2],q[++r]=tr[p].c[2];
else tr[p].c[2]=tr[tr[p].fail].c[2];
if(tr[p].c[3]) tr[tr[p].c[3]].fail=tr[tr[p].fail].c[3],q[++r]=tr[p].c[3];
else tr[p].c[3]=tr[tr[p].fail].c[3];
}
p=1;
for(int i=0;i!=n;++i) {p=tr[p].c[ch(s[i])]; if(p!=1) tr[p].dan=1;}
for(int i=r;i;--i) {p=q[i]; tr[tr[p].fail].dan|=tr[p].dan;}
if(tr[1].c[0]!=1) tr[tr[1].c[0]].ans=tr[tr[1].c[0]].dan;
if(tr[1].c[1]!=1) tr[tr[1].c[1]].ans=tr[tr[1].c[1]].dan;
if(tr[1].c[2]!=1) tr[tr[1].c[2]].ans=tr[tr[1].c[2]].dan;
if(tr[1].c[3]!=1) tr[tr[1].c[3]].ans=tr[tr[1].c[3]].dan;
for(int i=1;i<=r;++i)
{
p=q[i];
if(tr[tr[p].c[0]].dep==tr[p].dep+1) tr[tr[p].c[0]].ans=tr[tr[p].c[0]].dan?tr[tr[p].c[0]].dep:tr[p].ans;
if(tr[tr[p].c[1]].dep==tr[p].dep+1) tr[tr[p].c[1]].ans=tr[tr[p].c[1]].dan?tr[tr[p].c[1]].dep:tr[p].ans;
if(tr[tr[p].c[2]].dep==tr[p].dep+1) tr[tr[p].c[2]].ans=tr[tr[p].c[2]].dan?tr[tr[p].c[2]].dep:tr[p].ans;
if(tr[tr[p].c[3]].dep==tr[p].dep+1) tr[tr[p].c[3]].ans=tr[tr[p].c[3]].dan?tr[tr[p].c[3]].dep:tr[p].ans;
}
for(int i=1;i<=m;++i) printf("%d\n",tr[ques[i]].ans);
return 0;
}