JSOI2012 玄武密码 和 HDU2222 Keywords Search
2024-08-27 00:19:22
玄武密码
给若干模式串和一个文本串.求每个模式串在文本串上能匹配的最大前缀长度.
N<=107,M<=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;
}
最新文章
- 前端试题本(Javascript篇)
- Mysqli封装
- javascript 闭包最简单理解
- 依赖注入Bean属性
- 联系人的侧边字母索引ListView 将手机通讯录姓名通过首字母排序。
- Jquery选择器,操作DOM
- android开发学习 几个有用的学习资料~
- 杭电1162Eddy&;#39;s picture
- Java设计模式:生成器模式
- noip普及组2007 守望者的逃离
- python_怎么格式化字符串?
- python_非阻塞套接字及I/O流
- thinkPHP中M()和D()的区别
- (转载)intellj idea 如何设置类头注释和方法注释
- POJ 1177 Picture(线段树周长并)
- form表单target的用法
- hadoop集群操作常用命令
- 关于 JVM 内存的 N 个问题(转)
- 在Linux中安装Oracle(较详细图解)
- KETTLE:mongdb与mysql互传数据
热门文章
- 【leetcode算法-简单】7.整数反转
- 6、2、2 存到redis 中的验证码
- 《ucore lab8》实验报告
- as报错 Multiple root tags Unexpected tokens 这个都是编译器识别问题
- PHP被忽略的基础知识
- 转:对JavaScript中闭包的理解
- 关于tomcat9的startup.bat闪退问题&;乱码
- 阿里云服务器安装mysql8遇到的问题
- 查看IIS错误日志
- java.lang.NoClassDefFoundError: org/springframework/core/env/EnvironmentCapa