NC50352. 玄武密码
描述
输入描述
第一行有两个整数，N和M，分别表示母串的长度和文字段的个数；
第二行是一个长度为N的字符串，所有字符都满足是E，S，W和N中的一个；
之后M行，每行有一个字符串，描述了一段带有玄武密码的文字。依然满足，所有字符都满足是E，S，W和N中的一个。
输出描述
输出有M行，对应M段文字。
每一行输出一个数，表示这一段文字的前缀与母串的最大匹配串长度。
示例1
输入:
7 3 SNNSSNS NNSS NNN WSEE
输出:
4 2 0
C++(clang++11) 解法, 执行用时: 81ms, 内存消耗: 14316K, 提交时间: 2020-11-29 11:32:10
#include<bits/stdc++.h>
#define ep emplace
using namespace std;
const int mt=10201129;
bool rea[mt];
int n,m,u,v,i,j,tot=1,to;
int nxt[mt],ans[mt],a[mt][5];
string s,t[101129];
queue<int>q;
int dir(char ch){
if(ch=='E')return 0;
if(ch=='S')return 1;
if(ch=='W')return 2;
if(ch=='N')return 3;
return 4;
}int main(){
int len;
a[0][0]=a[0][1]=a[0][2]=a[0][3]=1;
q.push(1),scanf("%d%d",&n,&m),cin>>s;
for(i=0;i<m;i++){
cin>>t[i],len=t[i].length();
for(u=1,j=0;j<len;j++){
to=dir(t[i][j]);
if(!a[u][to])a[u][to]=++tot;
u=a[u][to];
}
}for(;!q.empty();q.pop()){
u=q.front();
for(i=0;i<4;i++)
if(a[u][i])q.ep(a[u][i]),nxt[a[u][i]]=a[nxt[u]][i];
else a[u][i]=a[nxt[u]][i];
}for(u=1,i=0;i<n;i++){
u=a[u][dir(s[i])];
for(v=u;v&&!rea[v];v=nxt[v])
rea[v]=true;
}for(i=0;i<m;i++){
len=t[i].length();
for(u=1,j=0;j<=len;j++)
if(!rea[u=a[u][dir(t[i][j])]]){
printf("%d\n",j);
break;
}
}return 0;
}