一开始千方百计地想要对那个“母串”进行什么处理，最后也没有想出点什么。
后来发现这道题有点误导性，它没有说是“模式串”，而说是“询问”，因此就比较恶心。
闲话少说，这题正解是将“询问”离线建自动AC机，然后将“母串”丢进去匹配。（就是最模板的操作）
最后将“询问”丢进匹配好的AC机里去，枚举它的所有点，找到层数最深的有标记的点，则深度即为答案。
关键代码：
int ask(int id){
int x=1,res=0;
for(int i=0;i<S;i++){
x=t[x].ch[hs(dict[id][i])];
if(t[x].tms)res=i+1;
}
return res;
}
(hs)函数将给出的四个字母(('E','S','W','N'))映射成一个([0,4))内的(int)。
(dict)就是询问。
总代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,S,cnt=1;
char s[10010000],dict[100100][110];
struct AC_Automaton{
int ch[4],fail,in,tms;
}t[10010000];
int hs(char x){
if(x=='E')return 0;
if(x=='S')return 1;
if(x=='W')return 2;
if(x=='N')return 3;
}
inline void ins(int id){
int x=1;
for(int i=0;i<S;i++){
if(!t[x].ch[hs(dict[id][i])])t[x].ch[hs(dict[id][i])]=++cnt;
x=t[x].ch[hs(dict[id][i])];
}
}
queue<int>q;
inline void build(){
for(int i=0;i<4;i++){
if(t[1].ch[i])t[t[1].ch[i]].fail=1,q.push(t[1].ch[i]),t[1].in++;
else t[1].ch[i]=1;
}
while(!q.empty()){
int x=q.front();q.pop();
for(int i=0;i<4;i++){
if(t[x].ch[i])t[t[x].ch[i]].fail=t[t[x].fail].ch[i],q.push(t[x].ch[i]),t[t[t[x].fail].ch[i]].in++;
else t[x].ch[i]=t[t[x].fail].ch[i];
}
}
}
void merge(){
int x=1;
for(int i=0;i<S;i++){
x=t[x].ch[hs(s[i])];
t[x].tms++;
}
}
void topo(){
for(int i=1;i<=cnt;i++)if(!t[i].in)q.push(i);
while(!q.empty()){
int x=q.front();q.pop();
t[t[x].fail].tms+=t[x].tms;
t[t[x].fail].in--;
if(!t[t[x].fail].in)q.push(t[x].fail);
}
}
int ask(int id){
int x=1,res=0;
for(int i=0;i<S;i++){
x=t[x].ch[hs(dict[id][i])];
if(t[x].tms)res=i+1;
}
return res;
}
int main(){
scanf("%d%d",&n,&m);
scanf("%s",s);
for(int i=0;i<m;i++)scanf("%s",dict[i]),S=strlen(dict[i]),ins(i);
build();
S=n;
merge();
topo();
for(int i=0;i<m;i++)S=strlen(dict[i]),printf("%d
",ask(i));
return 0;
}