如题 TLE一半点

#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int mn=1e7+10;
int ch[mn][5];
int cnt[mn];
int fail[mn];
int ans;
int n,m;
char mc[mn];
char st[100050][150];

int len(char *s)
{
	return strlen(s);
}

int zs(char s)
{
	if(s=='E') return 1;
	if(s=='S') return 2;
	if(s=='W') return 3;
	if(s=='N') return 4;
}

void insert(char *s)
{
	int u=0;
	for(int i=0;i<len(s);i++)
	{
		int c=zs(s[i]);
		if(!ch[u][c])
			ch[u][c]=++ans;
		u=ch[u][c];
	}
}

void bfs()
{
	queue<int> q;
	int u=0;
	for(int i=1;i<=4;i++)
	{
		if(ch[u][i])
			q.push(ch[u][i]);
	}
	while(!q.empty())
	{
		int now=q.front();
		q.pop();
		for(int i=1;i<=4;i++)
		{
			if(ch[now][i])
			{
				fail[ch[now][i]]=ch[fail[now]][i];
				q.push(ch[now][i]);
			}
			else
			ch[now][i]=ch[fail[now]][i];
		}
	}
}

void ask(char *s)
{
	int u=0;
	for(int i=0;i<len(s);i++)
	{
		int now=zs(s[i]);
		u=ch[u][now];
		for(int j=u;j&&!cnt[j];j=fail[j])
		{
		//	if(cnt[j]) break;
			cnt[j]=1;
		}
	}
}

int query(char *s)
{
	int anss=0;
	int u=0;
	for(int i=0;i<len(s);i++)
	{
		int now=zs(s[i]);
		u=ch[u][now];
		if(cnt[u]) anss=i+1;
	}
	return anss;
}

int main()
{
	//ios::sync_with_stdio(false);
	scanf("%d%d",&n,&m);
	scanf("%s",mc);
	for(int i=1;i<=m;i++)
	{
		scanf("%s",st[i]);
		insert(st[i]);
	}
	bfs();
	ask(mc);
	for(int i=1;i<=m;i++)
	{
		printf("%d\n",query(st[i]));
	}
	return 0;
}