字首比對
題目
解析
查詢串考慮字首,故不難想到拿查詢串建,母串跑,跑到的點的 n x t nxt nxt顯然也合法,跳失配标記,就标記出了母串的子串
然後再拿查詢串跑一遍,就好了
code:
#include<queue>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
inline int f(char s){return (s=='S')?0:((s=='E')?1:((s=='W')?2:3));}
struct AC_easy
{
int tot=1,q,ch[1000010][4],nxt[1000010],val[1000010],k;
queue <int> b;
inline void insert(char *s)
{
int len=strlen(s),now=1;
for(int i=0;i<len;++i)
{
if(!ch[now][f(s[i])])ch[now][f(s[i])]=++tot;
now=ch[now][f(s[i])];
}
}
inline void bfs()
{
for(int i=0;i<=3;++i)ch[0][i]=1;
b.push(1);
while(b.size())
{
k=b.front(),b.pop();
for(int i=0;i<=3;++i)
{
if(!ch[k][i])ch[k][i]=ch[nxt[k]][i];
else nxt[ch[k][i]]=ch[nxt[k]][i],b.push(ch[k][i]);
}
}
}
inline void bfs2(char *s)
{
int len=strlen(s),now=1,q;
for(int i=0;i<len;++i){now=q=ch[now][f(s[i])];while(q)val[q]=1,q=nxt[q];}
}
inline int ask(char *s)
{
int len=strlen(s),now=1,ans=0;
for(int i=0;i<len;++i)now=ch[now][f(s[i])],ans=val[now]?(i+1):ans;
return ans;
}
}AC;
char s[10000010],q[100010][110];
int n;
int main()
{
scanf("%d%d%s",&n,&n,&s);
for(int i=1;i<=n;++i)scanf("%s",&q[i]),AC.insert(q[i]);
AC.bfs(),AC.bfs2(s);
for(int i=1;i<=n;++i)printf("%d\n",AC.ask(q[i]));
return 0;
}