http://acm.hdu.edu.cn/showproblem.php?pid=2896

另一道AC自动机的模板题,不过这题需要记录一下具体的匹配情况。

/*--------------------------------------------------------------------------------------*/
// Helica's header
// Second Editions
// 2015.11.7
//
#include <algorithm>
#include <iostream>
#include <cstring>
#include <ctype.h>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map> //debug function for a N*M array
#define debug_map(N,M,G) printf("\n");for(int i=0;i<(N);i++)\
{for(int j=;j<(M);j++){\
printf("%d",G[i][j]);}printf("\n");}
//debug function for int,float,double,etc.
#define debug_var(X) cout<<#X"="<<X<<endl;
/*--------------------------------------------------------------------------------------*/
using namespace std; int N,M,T;
int tol; struct Trie
{
int next[][],fail[],end[];
int num[];
int root,L;
int cnt;
int newnode()
{
for(int i=;i<;i++)
next[L][i] = -;
end[L++] = ;
return L-;
}
void init()
{
L = ;
root = newnode();
memset(num,,sizeof num);
cnt = ;
}
void insert(char *s)
{
int len = strlen(s);
int now = root;
for(int i=;i<len;i++)
{
if(next[now][s[i]-'!'] == -)
next[now][s[i]-'!'] = newnode();
now = next[now][s[i]-'!'];
}
end[now]++;
num[now] = cnt++;
}
void build()
{
queue <int> Q;
fail[root] = root;
for(int i=;i<;i++)
{
if(next[root][i] == -)
next[root][i] = root;
else
{
fail[next[root][i]] = root;
Q.push(next[root][i]);
}
}
while(! Q.empty())
{
int now = Q.front();
Q.pop();
for(int i=;i<;i++)
{
if(next[now][i] == -)
next[now][i] = next[fail[now]][i];
else
{
fail[next[now][i]] = next[fail[now]][i];
Q.push(next[now][i]);
}
}
}
}
void query(char *s,int no)
{
int len = strlen(s);
int now = root;
int ans = ;
set <int > web; for(int i=;i<len;i++)
{
now = next[now][s[i]-'!'];
int temp = now;
while(temp != root)
{
ans += end[temp];
if(end[temp]) web.insert(num[temp]);
temp = fail[temp];
}
}
if(!web.empty())
{
printf("web %d:",no);
for(set <int>::iterator it=web.begin();it != web.end();it++)
printf(" %d",*it);
printf("\n");
tol++;
}
}
}ac; char buf[]; int main()
{
while(~scanf("%d",&N))
{
ac.init();
tol = ;
for(int i=;i<N;i++)
{
scanf("%s",buf);
ac.insert(buf);
}
ac.build();
scanf("%d",&M);
for(int i=;i<=M;i++)
{
scanf("%s",buf);
ac.query(buf,i);
}
printf("total: %d\n",tol);
}
}

最新文章

  1. ssh 公钥登陆的问题
  2. Util应用程序框架公共操作类(八):Lambda表达式公共操作类(二)
  3. Spring 4 官方文档学习(十三)集成其他web框架
  4. nodejs图片转换字节保存
  5. 大话设计模式C++版——代理模式
  6. Android中事件传递机制的总结
  7. 移动端前端常见的触摸相关事件touch、tap、swipe等整理
  8. apache2.2 虚拟主机配置
  9. switch的case中不能做定义
  10. configure脚本参数介绍
  11. win7禁止自动使用浏览器打开FTP而是用资源管理器
  12. Message Authentication Code
  13. Repeater数据绑定和操作
  14. Java图形化界面设计——布局管理器之BorderLayout(边界布局)
  15. [20190417]隐含参数_SPIN_COUNT.txt
  16. 随心测试_数据库_002 &lt;数据库系统组成&gt;
  17. SQL基础语法提纲
  18. leetcode [34] Find First and Last Position of Element in Sorted Array
  19. 百度开放平台连接MySQL数据库
  20. 洛谷 P4910 帕秋莉的手环 矩阵乘法+快速幂详解

热门文章

  1. android 权限动态申请
  2. 一、java虚拟机内存区域
  3. PHP_EOL换行 与 base64编码
  4. C#中当程序的访问权限不足时,Directory.Exists和File.Exists方法不会抛出异常报错
  5. vue 动态加载组建
  6. 浅谈MySQL引擎(纯个人理解,如有错误请指正)
  7. SSL踩坑ERR_SSL_VERSION_OR_CIPHER_MISMATCH
  8. Roslyn入门(一)-C#语法分析
  9. PyCharm Tips 常用操作帮助
  10. 牛客训练赛25-A-因数个数