显然是AC自动机对吧
插入单词之后把文章在自动机上跑一遍，到达过的节点打上花火标记
之后检查一下每个单词有几个标记即可
可以把题目中的4个字母映射成abcd方便遍历
一定要记得把文章也映射啊！
#include<cstdio> #include<iostream> #include<cstring> #include<queue> using namespace std; const int N=1e7+5; char word[100005][105],s[N]; int n,m; char mapping(char ch) { switch(ch) { case 'E':return 'a';break; case 'S':return 'b';break; case 'W':return 'c';break; case 'N':return 'd';break; } } struct AC_auto { struct node { node *son[7],*fail,*fa; int size; bool v; node() { memset(this,0,sizeof(node)); } }; node *root; void ini() { root=new node; } void ins(char *str) { int l=strlen(str+1); node *now=root; for(int i=1;i<=l;i++) { if(!now->son[str[i]-'a']) now->son[str[i]-'a']=new node(); now=now->son[str[i]-'a']; } now->size++; } void build() { queue<node*> q; for(int i=0;i<4;i++) { if(root->son[i]) { q.push(root->son[i]); root->son[i]->fail=root; } else root->son[i]=root; } while(!q.empty()) { node *x=q.front(); q.pop(); for(int i=0;i<4;i++) { if(x->son[i]) { x->son[i]->fail=x->fail->son[i]; q.push(x->son[i]); } else x->son[i]=x->fail->son[i]; } } } void query(char *str) { node *now=root; int l=strlen(str+1),i=1; while(i<=l) { now=now->son[str[i]-'a']; if(!now)return ; for(node *j=now;j!=root&&j->size!=-1;j=j->fail) j->size=-1; i++; } } int ans(char *str) { node *now=root; int l=strlen(str+1),i; for(i=1;i<=l;i++) { if(now->son[str[i]-'a']->size>=0)break; now=now->son[str[i]-'a']; } return i-1; } }ac; int main() { scanf("%d%d%s",&n,&m,s+1); for(int i=1;i<=n;i++)s[i]=mapping(s[i]);//Don't forget it! ac.ini(); for(int i=1;i<=m;i++) { scanf("%s",word[i]+1); int l=strlen(word[i]+1); for(int j=1;j<=l;j++)word[i][j]=mapping(word[i][j]); ac.ins(word[i]); } ac.build(); ac.query(s); for(int i=1;i<=m;i++)printf("%d ",ac.ans(word[i])); return 0; }