听说这题不公开.. 那就不贴题意了
一眼看上去还以为是exkmp的裸题.. 看了数据范围，呵呵..
多串匹配嘛.. 就用AC自动机咯，而且每个点最多也就只有$4$个孩子
用原串在AC自动机上走，碰到的和fail到的都是可以到达的字符串，每个点标记记录一下，这个时间复杂度是$O(n)$的
然后再每个串走AC自动机，找到最远的被标记的点就是答案了..
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;
const int Maxn = ;
const int Maxm = ;
struct trie {
int child[], fl, fail;
}tr[Maxm]; int tot, rt;
char s[Maxm], st[Maxn][]; int n, stl[Maxn];
int m;
int get ( char c ){
if ( c == 'N' ) return ;
if ( c == 'W' ) return ;
if ( c == 'E' ) return ;
return ;
}
void bulid ( int &now, int l, int x ){
if ( !now ) now = ++tot;
if ( l == stl[x]+ ) return;
bulid ( tr[now].child[get(st[x][l])], l+, x );
}
void bulid_ac (){
queue <int> q;
q.push (rt);
while ( !q.empty () ){
int x = q.front (); q.pop ();
for ( int i = ; i < ; i ++ ){
int y = tr[x].child[i];
if ( !y ){
if ( x == rt ) tr[x].child[i] = x;
else tr[x].child[i] = tr[tr[x].fail].child[i];
}
else {
if ( x == rt ) tr[y].fail = x;
else tr[y].fail = tr[tr[x].fail].child[i];
}
if ( y > ) q.push (y);
}
}
}
int find ( int now, int l, int x ){
if ( l == stl[x]+ ) return stl[x];
if ( tr[tr[now].child[get(st[x][l])]].fl == ) return l-;
return find ( tr[now].child[get(st[x][l])], l+, x );
}
int main (){
int i, j, k;
scanf ( "%d%d", &n, &m );
scanf ( "%s", s+ );
for ( i = ; i <= m; i ++ ){
scanf ( "%s", st[i]+ );
stl[i] = strlen (st[i]+);
bulid ( rt, , i );
}
bulid_ac ();
int now = rt;
for ( i = ; i <= n; i ++ ){
now = tr[now].child[get(s[i])];
int x = now;
while ( tr[x].fl == && x ){
tr[x].fl = ;
x = tr[x].fail;
}
}
for ( i = ; i <= m; i ++ ){
printf ( "%d\n", find ( rt, , i ) );
}
return ;
}