Keywords Search AC自动机
2024-08-30 22:25:29
In the modern time, Search engine came into the life of everybody like Google, Baidu, etc.
Wiskey also wants to bring this feature to his image retrieval system.
Every image have a long description, when users type some keywords to find the image, the system will match the keywords with description of image and show the image which the most keywords be matched.
To simplify the problem, giving you a description of image, and some keywords, you should tell me how many keywords will be match.
Wiskey also wants to bring this feature to his image retrieval system.
Every image have a long description, when users type some keywords to find the image, the system will match the keywords with description of image and show the image which the most keywords be matched.
To simplify the problem, giving you a description of image, and some keywords, you should tell me how many keywords will be match.
InputFirst line will contain one integer means how many cases will follow by.
Each case will contain two integers N means the number of keywords and N keywords follow. (N <= 10000)
Each keyword will only contains characters 'a'-'z', and the length will be not longer than 50.
The last line is the description, and the length will be not longer than 1000000.
OutputPrint how many keywords are contained in the description.Sample Input
1
5
she
he
say
shr
her
yasherhs
Sample Output
3
AC自动机:利用ttie树节省空间,利用kmp相似的原理构建fail指针进行匹配
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<queue>
#include<deque>
#include<iomanip>
#include<vector>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<fstream>
#include<memory>
#include<list>
#include<string>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MAXN 26
#define L 31
#define INF 1000000009
#define eps 0.00000001
struct node
{
node()
{
cnt = ;
fail = NULL;
for (int i = ; i < MAXN; i++)
next[i] = NULL;
}
int cnt;
struct node* next[MAXN];
struct node* fail;
};
typedef struct node* Tree;
void insert(Tree T, const char* str)
{
int p = ;
Tree tmp = T;
while (str[p] != '\0')
{
int k = str[p] - 'a';
if (tmp->next[k] == NULL)
{
tmp->next[k] = new node();
}
tmp = tmp->next[k];
p++;
}
tmp->cnt++;
}
void build_ac(Tree root)
{
root->fail = NULL;
queue<Tree> q;
q.push(root);
while (!q.empty())
{
Tree tmp = q.front();
q.pop();
Tree p = NULL;
for (int i = ; i < MAXN; i++)
{
if (tmp->next[i] != NULL)
{
if (tmp == root)
tmp->next[i]->fail = root;
else
{
p = tmp->fail;
while (p != NULL)
{
if (p->next[i] != NULL)
{
tmp->next[i]->fail = p->next[i];
break;
}
p = p->fail;
}
if (p == NULL) tmp->next[i]->fail = root;
}
q.push(tmp->next[i]);
}
}
}
}
int query(Tree root,const char* str)
{
int i = ;
int count = ;
int l = strlen(str);
Tree tmp = root;
int index;
while (str[i])
{
index = str[i] - 'a';
while (tmp->next[index] == NULL && tmp != root)
tmp = tmp->fail;
tmp = tmp->next[index];
if (tmp == NULL) tmp = root;
Tree p = tmp;
while (p != root)
{
count += p->cnt;
p->cnt = ;
p = p->fail;
}
i++;
}
return count;
} void del(Tree root)
{
for (int i = ; i < MAXN; i++)
if (root->next[i] != NULL)
del(root->next[i]);
delete root;
}
char key[], s[];
int main()
{
int T, n;
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
Tree root = new node();
root->cnt = ;
root->fail = NULL;
for (int i = ; i < MAXN; i++)
root->next[i] = NULL;
for (int i = ; i < n; i++)
{
scanf("%s", key);
insert(root, key);
}
build_ac(root);
scanf("%s", s);
printf("%d\n", query(root, s));
del(root);
}
}
最新文章
- C# 对象实例化 用json保存 泛型类 可以很方便的保存程序设置
- springmvc No mapping found for HTTP request with URI in Dispatc
- (转)freemakeer初入门
- POJ1149 PIGS (网络流)
- [Python] UTF-8最好不要带BOM
- HDU-1335 Basically Speaking
- 2015-09-28Javascript(一)
- TrimPath - Js模板引擎
- C# - 委托_求定积分通用方法
- IE兼容问题及处理
- 【CSS】思考和再学习——关于CSS中浮动和定位对元素宽度/外边距/其他元素所占空间的影响
- MySQL的备份与还原以及常用数据库查看命令
- 前端自动化(三) 合并压缩css、压缩js、添加时间戳、打包上线操作
- <;3>;Centos系统完整安装python流程
- struts2 升级至2.3.32时访问页面报错 File ";/struts-tags"; not found
- Web上传文件的原理及实现
- yum安装tomcat
- Python学习笔记系列——读写文件以及敏感词过滤器的实现
- P1569 [USACO11FEB]属牛的抗议
- 【leetcode 简单】 第一百一十一题 可怜的小猪