玄武密码
给若干模式串和一个文本串.求每个模式串在文本串上能匹配的最大前缀长度.
N<=105，每一段文字的长度<=100。
jklover的题解
将模式串建成一个 AC 自动机,匹配文本串的时候往前暴力跳,跳到第一个合法的位置即可.
时间复杂度：线性。
co int N=1e7+1,S=4;
int n,m;
int len[N];
namespace AC
{
int idx;
int id(char x)
{
switch(x)
{
case 'E':
return 0;
case 'W':
return 1;
case 'N':
return 2;
case 'S':
return 3;
default:
assert(0);
}
}
int ch[N][S],fa[N],fail[N];
int marked[N],val[N];
void ins(char s[],int v)
{
int u=0;
for(int i=0;i<len[v];++i)
{
int k=id(s[i]);
if(!ch[u][k])
{
fa[++idx]=u;
ch[u][k]=idx;
}
u=ch[u][k];
}
val[v]=u;
}
void getfail()
{
std::queue<int>Q;
for(int i=0;i<S;++i)
if(ch[0][i])
Q.push(ch[0][i]);
while(Q.size())
{
int u=Q.front();Q.pop();
for(int i=0;i<S;++i)
{
if(ch[u][i])
{
fail[ch[u][i]]=ch[fail[u]][i];
Q.push(ch[u][i]);
}
else
ch[u][i]=ch[fail[u]][i];
}
}
}
void mark(char*s)
{
int u=0;
for(int i=0;i<n;++i)
{
int k=id(s[i]);
u=ch[u][k];
for(int j=u;j&&!marked[j];j=fail[j])
marked[j]=1;
}
}
int work(int x)
{
int ans=len[x];
for(int i=val[x];i;i=fa[i],--ans)
if(marked[i])
return ans;
}
}
char buf[110];
char s[N];
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n),read(m);
scanf("%s",s);
for(int i=1;i<=m;++i)
{
scanf("%s",buf);
len[i]=strlen(buf);
AC::ins(buf,i);
}
AC::getfail();
AC::mark(s);
for(int i=1;i<=m;++i)
{
int ans=AC::work(i);
printf("%d\n",ans);
}
return 0;
}
Keywords Search
给若干个模式串,再给一个文本串,问有几个模式串在文本串中出现过.
jklover的题解
板子题.注意一个模式串只被计算一次,统计后做上标记.
这里采用的是补全 Trie 树的写法.
时间复杂度线性。主要是找出现的这里：
for(int j=u;j&&val[j]!=-1;j=fail[j])
res+=val[j],val[j]=-1;
但这里每个节点最多访问一次，也是线性的。
可以用蓝书上的last代替。
代码
HDU不给用<bits/stdc++.h>……
co int N=5e5+1,S=26;
namespace AC
{
int idx;
int ch[N][S],fail[N],val[N];
void init()
{
idx=0;
memset(val,0,sizeof val);
memset(ch,0,sizeof ch);
memset(fail,0,sizeof fail);
}
void ins(char s[],int n)
{
int u=0;
for(int i=0;i<n;++i)
{
int k=s[i]-'a';
if(!ch[u][k])
ch[u][k]=++idx;
u=ch[u][k];
}
++val[u];
}
void getfail()
{
std::queue<int>Q;
for(int i=0;i<S;++i)
if(ch[0][i])
Q.push(ch[0][i]);
while(Q.size())
{
int u=Q.front();Q.pop();
for(int i=0;i<S;++i)
{
if(ch[u][i])
{
fail[ch[u][i]]=ch[fail[u]][i];
Q.push(ch[u][i]);
}
else
ch[u][i]=ch[fail[u]][i];
}
}
}
int query(char s[],int n)
{
int u=0,res=0;
for(int i=0;i<n;++i)
{
int k=s[i]-'a';
u=ch[u][k];
for(int j=u;j&&val[j]!=-1;j=fail[j])
res+=val[j],val[j]=-1;
}
return res;
}
}
char buf[N*2];
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int t;
read(t);
while(t--)
{
AC::init();
int n;
read(n);
for(int i=1;i<=n;++i)
{
scanf("%s",buf);
AC::ins(buf,strlen(buf));
}
AC::getfail();
scanf("%s",buf);
int ans=AC::query(buf,strlen(buf));
printf("%d\n",ans);
}
return 0;
}