Rt，思路是建完AC之后用主串标记能遍历到的AC上的点，然后用模式串再找一遍最长的长度

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
string T;
int n,m;
struct node
{
    int vis[5];
    int fail;
    int end;
}c[10000005];
//int match[1000005];
int cnt;
string ask[100005];
inline int getsum(char a)
{
    if(a=='E') return 1;
    if(a=='S') return 2;
    if(a=='W') return 3;
    if(a=='N') return 4;
}
inline void insert(string s,int num)
{
    int len=s.size();
    int pos=0;
    for(register int i=0; i<len;i++)
    {
        int k=getsum(s[i]);
        if(!c[pos].vis[k])
        {
            c[pos].vis[k]=++cnt;
        }
    }
  //  match[num]=pos;
}
inline void build()
{
    queue<int> q;
    for(register int i=1; i<=4;i++)
    {
        if(c[0].vis[i])
        {
            c[c[0].vis[i]].fail=0;
            q.push(c[0].vis[i]);
        }
    }
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(register int i=1; i<=4;i++)
        {
            if(c[now].vis[i])
            {
                c[c[now].vis[i]].fail=c[c[now].fail].vis[i];
                q.push(c[now].vis[i]);
            }
            else c[now].vis[i]=c[c[now].fail].vis[i];
        }
    }
}
inline void query(string s)
{
    int pos=0;
    int len=s.size();
    for(register int i=0; i<len;i++)
    {
        int k=getsum(s[i]);
        pos=c[pos].vis[k];
        for(register int j=pos;j;j=c[j].fail)
        {
            if(c[j].end) break;
            c[j].end=1;
        }
    }
    for(register int i=1; i<=m;i++)
    {
        int res=0,p=0;
        for(register int j=0; j<ask[i].size();j++)
        {
            p=c[p].vis[getsum(ask[i][j])];
            if(c[p].end) res=j+1;
        }
        printf("%d\n",res);
    }
}
int main()
{
    cin>>n>>m>>T;
    for(register int i=1; i<=m;i++)
    {
        cin>>ask[i];
        insert(ask[i],i);
    }
    build();
    query(T);
    return 0;
}