HDU 3065 (AC自动机模板题)
2024-08-26 19:47:56
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=3065
题目大意:多个模式串,范围是大写字母。匹配串的字符范围是(0~127)。问匹配串中含有哪几种模式串,且每种模式串出现了多少次。
解题思路:
AC自动机模板题。模式串的范围是大写字母,但是匹配串的范围却是(0~127).
如果Trie 开到 128 加上不回收内存,就会MLE。
实际上开到26就行了,find的时候对于c<0||c>26,强制令pos=root出现失配,并开始下一个字符就行了。
cnt记录这个模式串的个数改为这个模式串的index。
find的时候,把找到的index对应的HASH++,进行统计。
注意每次find时,无须修改last->cnt,因为统计模式串的次数必须让模式串走多遍,修改了之后相当于只走了一遍。
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include "cstdio"
#include "cstring"
#include "string"
#include "iostream"
#include "queue"
#include "vector"
#include "algorithm"
using namespace std;
#define maxn 26
int HASH[];
string code[];
struct Trie
{
Trie *next[maxn],*fail;
int cnt;
}*root;
struct status
{
Trie *last;
int cnt;
status(Trie *last,int cnt):last(last),cnt(cnt) {}
};
Trie *newnode()
{
Trie *ret=new Trie;
memset(ret->next,,sizeof(ret->next));
ret->fail=;
ret->cnt=;
return ret;
}
void init() {root=newnode();}
void Insert(string str,int index)
{
Trie *pos=root;
for(int i=;i<str.size();i++)
{
int c=str[i]-'A';
if(!pos->next[c]) pos->next[c]=newnode();
pos=pos->next[c];
}
pos->cnt=index;
}
void getfail()
{
queue<Trie *> Q;
for(int c=;c<maxn;c++)
{
if(root->next[c])
{
root->next[c]->fail=root;
Q.push(root->next[c]);
}
else root->next[c]=root;
}
while(!Q.empty())
{
Trie *x=Q.front();Q.pop();
for(int c=;c<maxn;c++)
{
if(x->next[c])
{
x->next[c]->fail=x->fail->next[c];
Q.push(x->next[c]);
}
else x->next[c]=x->fail->next[c];
}
}
}
void find(string str)
{
Trie *pos=root,*last;
queue<status> Q;
for(int i=;i<str.size();i++)
{
int c=str[i]-'A';last;
if(c<||c>maxn) {pos=root;continue;}
if(pos->next[c])
{
pos=pos->next[c];
last=pos;
while(last->cnt)
{
Q.push(status(last,last->cnt));
HASH[last->cnt]++;
//last->cnt=0; //修改last->cnt
last=last->fail;
}
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
ios::sync_with_stdio(false);
int n,m;
string tt;
while(cin>>n)
{
memset(HASH,,sizeof(HASH));
init();
for(int i=;i<=n;i++)
{
cin>>code[i];
Insert(code[i],i);
}
getfail();
cin>>tt;
find(tt);
for(int i=;i<=n;i++)
{
if(!HASH[i]) continue;
cout<<code[i]<<": "<<HASH[i]<<endl;
}
}
}
2872067 | neopenx | HDU | 3065 | Accepted | 16056 | 343 | C++ | 2469 |
2014-10-21 16:41:03
|
最新文章
- Metrics.NET 项目
- java中构造方法的特殊性
- javascript中元素的scrollLeft和scrollTop属性说明
- 一些java面试题
- c++ 复习练习
- Codeforces Round #303 (Div. 2) A 水
- 在Windows下通过命令行或者.bat文件统计一个目录中文件数量
- C#中使用自定义的纸张大小
- css重置样式表reset.css
- MySQL常用时间函数
- 关闭编译器FPO优化
- 2015暑假acm短训小结
- BZOJ 1614: [Usaco2007 Jan]Telephone Lines架设电话线
- perl 安装 ZooKeeper模块
- 小议 js 下字符串比较大小
- IOS学习之路七(通过xib自定义UITableViewCell)
- 深度学习框架Caffe的编译安装
- vue-router 二级路由
- [翻译] 编写高性能 .NET 代码--第二章 GC -- 将长生命周期对象和大对象池化
- IDEA创建applicationContext.xml 无法自动提示,文件图标是文本类型
热门文章
- [codeforces 509]C. Sums of Digits
- java笔试一
- CentOS6 下安装HP-LaserJet 1020打印机
- 【云计算】docker的小知识,帮你更深入理解容器技术
- 【OpenStack】OpenStack系列12之OpenStack自动化测试详解
- 有时间测试dism
- Android之查看网络图片和网页HTML
- java equals 和 ";=="; 比较
- Oracle如何操作级联删除
- SQL Server 2012 OFFSET/FETCH NEXT分页示例(转载)