解题关键:AC自动机模板题,注意字符匹配时若无法匹配,直接用%s即可。

 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=;
const int MAXN=;
int num,ans[],nn;
bool vis[];
bool flag=false;
struct Trie{//数组形式
int Next[MAXN][N],Fail[MAXN],End[MAXN],root,tot;//大小为所以匹配字符串的总和
int newnode(){//结构体内部用
for(int i=;i<N;i++) Next[tot][i]=-;
End[tot++]=;
return tot-;
}
void init(){
tot=;
root=newnode();
}
void insert(char buf[],int x){
int len=strlen(buf);
int now=root;//now是temp指针
for(int i=;i<len;i++){
int k=buf[i]-'0';
if(Next[now][k]==-) Next[now][k]=newnode();//next数组代表的是下一个字符索引
now=Next[now][k];
}
End[now]=x;//end数组是当前字符串的个数.字典中可能有相同的单词,若只算一次,改为1.
}
void build(){//构造fail指针,后缀是某些前缀
queue<int>que;
Fail[root]=root;
for(int i=;i<N;i++){
if(Next[root][i]==-) Next[root][i]=root;
else{
Fail[Next[root][i]]=root;
que.push(Next[root][i]);
}
}
while(!que.empty()){//bfs,会将所有的匹配子串都遍历到
int now=que.front();
que.pop();
for(int i=;i<N;i++){
if(Next[now][i]==-) Next[now][i]=Next[Fail[now]][i];
else{
Fail[Next[now][i]]=Next[Fail[now]][i];//fail指向最长的
que.push(Next[now][i]);
}
}
}
}
void query(char buf[]){
int len=strlen(buf),now=root;
for(int i=;i<len;i++){
now=Next[now][buf[i]-'0'];
int temp=now;
while(temp!=root){
if(End[temp]&&!vis[temp]) ans[nn++]=End[temp],vis[temp]=true,flag=true;
temp=Fail[temp];
}
}
}
}; Trie ac;
char buf[],buf2[],tmp[];
int n,m;
int main(){
while(scanf("%d%d",&m,&n)!=EOF){
memset(ans,,sizeof ans);
memset(vis,,sizeof vis);
nn=;
ac.init();
int t=;
flag=false;
for(int i=;i<=m;i++){
scanf("%s",tmp);
strcat(buf,tmp);
}
for(int i=;i<=n;i++){
scanf("%*s %*s %d] %s",&num,buf2);
ac.insert(buf2,num);
}
ac.build();//不要忘记build
ac.query(buf);
if(flag){
printf("Found key:");
for(int i=;i<nn;i++){
printf(" [Key No. %d]",ans[i]);
}
printf("\n");
}
else printf("No key can be found !\n");
}
return ;
}

最新文章

  1. 用Asp.net写自己的服务框架
  2. Eclipse配置PyDev插件来实现python开发环境
  3. 关于transition回调函数的几种写法
  4. 数位dp/记忆化搜索
  5. andriod ADB命令的使用
  6. Notepad++加上xml格式化的功能
  7. 复习一下SpringMVC的工作原理
  8. 关于 JAVA 中使用 Preferences 读写注册表时要注意的地方
  9. eclipse点击空白处自动打开项目
  10. PyCharm 如何远程连接服务器编写程序
  11. 在NSMutableArray中添加空元素:NSNull类的使用
  12. Postgres数据库维护
  13. Web服务器之Nginx详解(操作部分)
  14. Visual Studio生成webservice代理类
  15. PHP开发者成长图
  16. BZOJ 3489 A simple rmq problem 可持久化KDtree/二维线段树
  17. JAVA容器-重点总结与深度解析
  18. POJ_3468 A Simple Problem with Integers 【线段树区间查询+修改】
  19. AC日记——[SDOI2010]大陆争霸 洛谷 P3690
  20. c语言中有bool型变量吗?

热门文章

  1. android页面间传递对象
  2. Linux Setuid(SUID)和Setgid(SGID) sticky bit
  3. sublime 汇总
  4. &lt;转&gt;关于 error LNK2019:无法解析的外部符号 ,该符号在函数**中被引用的思考
  5. ElasticSearch 分页检索
  6. 2016年最值得新手程序猿阅读的书:《增长project师指南》
  7. 01 json方式封装通信接口
  8. Unable to run Kiwi tests on iOS8 device
  9. bjfu1332 简单动规
  10. EasyPlayer安卓Android流媒体播放器实现直播过程中客户端快照功能