rt

题目传送门

代码

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

int trie  [1000001][10];
int isend [1000001];
int q     [1000001];
int nxt   [1000001];
bool bj   [1000001]; 
int le    [1000001];
int tot;
int ans; 
char st   [1000001];
int father[1000001];//初始化

int change(char c)
{
	if(c=='E')
		return 1;
	if(c=='S')
		return 2;
	if(c=='W')
		return 3;
	if(c=='N')
		return 4;
} //字符转数字

void insert(int x)
{
	int u=1;
	le[x]=strlen(st);
	int len=strlen(st);
	for(int i=1;i<=len;i++)
	{
		int c=change(st[i-1]);
		if(!trie[u][c])
		{
			trie[u][c]=++tot;
			father[tot]=u;//标记父亲节点
		}
		u=trie[u][c];
	} 
	isend[x]=u;
	return;
} //trie字典树插入

void bfs()//BFS构建fail指针
{
	for(int i=1;i<=4;i++)
	{
		trie[0][i]=1;
	}
	q[1]=1;
	nxt[1]=0;
	int head=1,tail=1;//队列
	while(head<=tail)
	{
		int u=q[head];
		for(int i=1;i<=4;i++)
		{
			if(!trie[u][i])
				trie[u][i]=trie[nxt[u]][i];
			else//构建fail(nxt)指针
			{
				tail++;
				q[tail]=trie[u][i];
				nxt[trie[u][i]]=trie[nxt[u]][i];
			}
		}
		head++; 
	} 
}

void find(char s[])//搜索
{
	int u=1;
	int len=strlen(s);
	int k;
	for(int i=1;i<=len;i++)
	{
		int c=change(s[i-1]);
		u=trie[u][c];
		k=u;
		while(k)
		{
			if(bj[k])
				break;
			else
				bj[k]=true;//往上标记已搜节点
			k=nxt[k];
		}
	}
}

int getans(int x)//寻找已搜节点
{
	int endd=le[x];
	for(int i=isend[x];i;i=father[i])
	{
		if(bj[i])
			return endd;
		else
			endd--;
	}
} 

int main()
{
	char nor[1000001];
	int n,m;
	ans=0,tot=1;
	cin>>n>>m;
	cin>>nor;
	for(int i=1;i<=m;i++)
	{
		cin>>st;
		insert(i);
	}
	bfs();
	find(nor);
	for(int i=1;i<=m;i++)
		cout<<getans(i)<<endl;
}//读入什么的

算法：AC自动机

RE了三个点