HDU2222 Keywords Search
2024-09-16 10:42:37
本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作。
本文作者:ljh2000
作者博客:http://www.cnblogs.com/ljh2000-jump/
转载请注明出处,侵权必究,保留最终解释权!
Problem Description
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.
Input
First 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.
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.
Output
Print how many keywords are contained in the
description.
description.
Sample Input
1
5
she
he
say
shr
her
yasherhs
5
she
he
say
shr
her
yasherhs
Sample Output
3
正解:AC自动机
解题报告:
AC自动机裸题。联赛前复习模板的时候突然发现AC自动机自己不会打了...好气啊
这篇博客讲的非常详细:http://blog.csdn.net/niushuai666/article/details/7002823
当然我的AC自动机还加了一条优化,就是当前结点,如果没有某个儿子结点,那么就直接连接上fail指针所指的结点的这一个儿子结点,这样的话在find的时候就不用每次都不停地往上跳fail指针了,可以直接一路顺着走,当全图都没有这个结点的时候,就会走到root上去,所以很方便,而且很快。
//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <stack>
using namespace std;
typedef long long LL;
const int MAXN = ;
int n,cnt,tr[MAXN][];
int val[MAXN],vis[MAXN],ans;
int dui[MAXN],head,tail,f[MAXN]; inline int getint(){
int w=,q=; char c=getchar(); while((c<''||c>'') && c!='-') c=getchar();
if(c=='-') q=,c=getchar(); while (c>=''&&c<='') w=w*+c-'',c=getchar(); return q?-w:w;
} inline void read(){
int u=,now; char c;
do{
c=getchar(); if(c=='\n' || c=='\r') break;
now=c-'a'; if(!tr[u][now]) tr[u][now]=++cnt;
u=tr[u][now];
}while(c!='-');
val[u]++;
} inline void getfail(){
head=tail=; dui[++tail]=; int u,now,j;
while(head<tail) {
head++; u=dui[head];
for(int i=;i<;i++) {
if(tr[u][i]) {
now=tr[u][i]; j=f[u];
while(j && tr[j][i]==) j=f[j];
f[now]= tr[j][i]==now ? :tr[j][i];
dui[++tail]=now;
}
else tr[u][i]=tr[f[u]][i];
}
}
} inline void find(){
char c; int u=,now;
while(c=getchar()) {
if(c=='\n' || c=='\r') break;
now=c-'a'; u=tr[u][now];
vis[u]=;
}
for(int i=tail;i>=;i--) {
u=dui[i];
ans+=vis[u]*val[u];
vis[f[u]]|=vis[u];
}
} inline void work(){
int T=getint();
while(T--) {
cnt=; memset(tr,,sizeof(tr)); memset(vis,,sizeof(vis)); memset(val,,sizeof(val));
memset(f,,sizeof(f)); n=getint(); for(int i=;i<=n;i++) read();
getfail(); ans=;
find();
printf("%d\n",ans);
}
} int main()
{
work();
return ;
}
最新文章
- Uva 11732 strcmp() Anyone?
- Word中一些问题解决
- Wiki介绍
- FTP地址格式如下:“ftp://用户名:密码@FTP服务器IP”
- Memcached【Magent+Memcached】集群
- http-2.4.18 安装
- @RequestBody, @ResponseBody 注解详解
- linux 部分命令简单使用介绍-ssh、scp、less、tail、find、grep(持续添加)
- js取整
- WinJS Clipboard
- C控制语句--分支和跳转
- NYOJ 58 步数最少 【BFS】
- linux下使用crontab定时执行脚本
- Mahout canopy聚类
- 5、lvs使用进阶(01)
- (C/C++学习笔记) 二十四. 知识补充
- (转)ElasticSearch Java Api-检索索引库
- Thunder——Final发布
- 关于json中转义字符/正斜杠的问题。
- 说一说Servlet的生命周期