hdu 3065病毒侵袭持续中（ac自动机）
2024-10-06 10:31:04
题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=3065
中文题题意不解释了。
依旧稍微改一下ac自动机模版就能过了。还有一个坑点！是多组数据！！！
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int M = 5e4 + 10 , MM = 2e6 + 10 , N = 1e3 + 10;
char str[N][60] , sl[MM];
int Next[M][27] , fail[M] , End[M] , c[M / 10] , L , root , cnt , ans;
int newnode() {
for(int i = 0 ; i <= 26 ; i++) {
Next[L][i] = -1;
}
End[L++] = 0;
return L - 1;
}
void init() {
L = 0 , ans = 0;
root = newnode();
memset(c , 0 , sizeof(c));
}
void build(char s[]) {
int len = strlen(s);
int now = root;
for(int i = 0 ; i < len ; i++) {
int id = s[i] - 'A';
if(Next[now][id] == -1) {
Next[now][id] = newnode();
}
now = Next[now][id];
}
End[now] = ++ans;
}
void get_fail() {
queue<int>q;
fail[root] = root;
for(int i = 0 ; i <= 26 ; i++) {
if(Next[root][i] == -1) {
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 = 0 ; i <= 26 ; i++) {
if(Next[now][i] == -1) {
Next[now][i] = Next[fail[now]][i];
}
else {
fail[Next[now][i]] = Next[fail[now]][i];
q.push(Next[now][i]);
}
}
}
}
void match(char s[]) {
int len = strlen(s);
int now = root;
for(int i = 0 ; i < len ; i++) {
int id;
if(s[i] <= 'Z' && s[i] >= 'A') {
id = s[i] - 'A';
}
else {
id = 26;
}
now = Next[now][id];
int tmp = now;
while(tmp != root) {
if(End[tmp] > 0) {
c[End[tmp]]++;
}
tmp = fail[tmp];
}
}
}
int main()
{
int n;
while(scanf("%d" , &n) != EOF) {
init();
for(int i = 0 ; i < n ; i++) {
scanf("%s" , str[i + 1]);
build(str[i + 1]);
}
getchar();
get_fail();
gets(sl);
match(sl);
for(int i = 0 ; i < n ; i++) {
if(c[i + 1] != 0) {
printf("%s: %d\n" , str[i + 1] , c[i + 1]);
}
}
}
return 0;
}
最新文章
- linux下创建文件与目录时默认被赋予了什么样的权限?
- java的反射
- 【转】【C#】迭代器
- PowerDesigner中Table视图怎样同时显示Code和Name
- 【Android】进入Material Design时代
- alertdialog.builder 自定义弹窗
- 在web.xml中配置error-page
- Android反编译教程
- 使用SharePoint 2010的母版页
- 【UVA 10369】 Arctic Network （最小生成树）
- java——String的那边破事
- MFC常用控件CListCtrl 、CSliderCtrl、CToolTipCtrl、CTreeCtrl的自绘
- C#设计模式总结（转）
- bzoj:1681 [Usaco2005 Mar]Checking an Alibi 不在场的证明
- POJ-2349 Arctic Network---MST的第m长的边
- hive的高级查询（group by、 order by、 join 、 distribute by、sort by、 clusrer by、 union all等）
- SpringBoot配置activemq消息队列
- 通过全备+relaylog同步恢复被drop的库或表【转】
- Object.assign方法的使用
- 自学Linux Shell3.3-列表命令ls