度娘讲的很好……所以不懂就百度吧。。。
首先构造一颗trie,
然后bfs构造fail指针。
最后进行文章匹配,注意题目只要求出现出现几个关键字。
所以只要找到一个就标记一下,下次再找到不算。
比如
1
1
abc
abcabc
输出1
还有,单词有可能重复,
1
2
abc
abc
abc
输出2
#include<cstring>
#include<queue>
#define MAXN 1000000
#define SIG 26
using namespace std;
char str[MAXN];
int size, ans;
struct node {
int fail, cnt, next[SIG];
bool vis;
void Init() {
fail = cnt = 0;
vis = false;
memset(next, 0, sizeof(next));
}
};
node trie[MAXN];
inline int get(char ch) {
return ch - 'a';
}
void insert(char *s) {
int now, t;
for (now = 0; *s; s++) {
t = get(*s);
if (!trie[now].next[t]) {
trie[++size].Init();
trie[now].next[t] = size;
}
now = trie[now].next[t];
}
trie[now].cnt++; //记录以该结点为结束点的单词个数
}
void bfs() {
int now, i, temp;
queue<int> q;
q.push(0);
while (!q.empty()) {
now = q.front();
q.pop();
for (i = 0; i < SIG; i++) {
if (trie[now].next[i]) {
temp = trie[now].next[i];
if (now)
trie[temp].fail = trie[trie[now].fail].next[i];
q.push(temp);
} else
trie[now].next[i] = trie[trie[now].fail].next[i];
}
}
}
int find(char *str)
{
int ans=0;
for(int now=0;*str;str++)
{
int j=get(*str);
now=trie[now].next[j];
int tmp=now; //将当前点保存下来
while(tmp&&(~trie[tmp].cnt)) //顺着失配边找,把路上的值都加起来
{
ans+=trie[tmp].cnt;
trie[tmp].cnt=-1; //因为题目要求,只要找到一个关键字就可以了,下次再找到也无视它
tmp=trie[tmp].fail;
}
}
return ans;
}
int main()
{
int t,n;
scanf("%d",&t);
char a[60];
while(t--)
{
size=0;
trie[0].Init();
scanf("%d",&n);
while(n--)
{
scanf("%s",a);
insert(a);
}
bfs();
scanf("%s",str);
printf("%d\n",find(str));
}
return 0;
}
分享到:
相关推荐
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
"HDU最全ac代码"这个压缩包很可能是包含了在HDU平台上解题通过的完整源代码集合,旨在帮助学习者理解和掌握各种算法,提升编程解决问题的能力。 首先,我们来了解一下ACM/ICPC比赛。这是一项全球性的编程竞赛,参赛...
一款 HDU OJ 的自动刷题工具,搜索来源可选用 百度搜索 / 必应搜索,支持并行以及串行查找,祝早日刷上航电首页哦~ 使用 Python 编写,执行之前你需要在同目录下创建文件 aclog.txt ,然后粘贴进你目前已经 AC 的...
HDU 300+ AC 代码集合是一个包含超过300个已通过验证的算法解决方案的资源,这些代码主要用于解决各类计算机编程竞赛中的问题。这些竞赛通常由杭州电子科技大学(HDU)主办,旨在提升参赛者的算法设计、编程和问题...
hdu2101AC代码
一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了
"AC"代表"Accepted",意味着提交的代码已经被评测系统接受,成功通过了所有测试用例。这个压缩包中的代码可能是用户在解决HDU平台上的编程题目时编写的,时间跨度从2000年至2014年。 从描述中我们可以推测,这个...
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
6. **字符串处理**:KMP匹配、Z算法、后缀数组、AC自动机等。 通过分析和理解这些代码,你可以提升自己的算法思维,学习如何高效地解决问题,这对于参加ACM竞赛或者日常的编程工作都非常有益。同时,也可以借鉴代码...
这些代码是针对HDU(杭州电子科技大学在线评测系统)的四道编程题目提交的AC(Accepted)解决方案。每段代码对应一个不同的问题,下面是每个问题的简要说明及代码解析: 1. HDU 2072 - 字符串处理 这个问题涉及到...
"HDU AC code"是一个与编程竞赛相关的压缩包文件,主要包含了作者在参与杭州电子科技大学(HDU)在线评测系统(Online Judge,简称OJ)时成功通过(Accepted,AC)的代码。这些代码通常涉及各种算法和数据结构,旨在...
HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...
【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...
ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...
### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...
【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...
HDU1059的代码
这份资源包含超过3000个已通过验证(AC,Accepted)的代码实例,覆盖了HDU平台上的各种题目类型,从基础的数据结构和算法到复杂的问题解决策略,无不包含其中。每一个代码实例都是一个珍贵的学习素材,它们不仅是...
"AC"是编程比赛中常用的术语,代表"Accepted",意味着你的代码已经正确解决了题目所提出的问题,并通过了所有测试用例。 从提供的文件名来看,这些是针对HDU题目的C++源代码文件,具体题目编号包括1007、10071、...