hdu2222Keywords Search

时间:2022-09-22 20:57:05
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.
 
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.
 
Output
Print how many keywords are contained in the description.
 
Sample Input
1 5 she he say shr her yasherhs
 
Sample Output
3
 
Author
Wiskey
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue> using namespace std; struct node
{
node* next[];
int end;
node* fail;
node()
{
for(int i = ;i<;i++)
next[i] = NULL;
fail = NULL;
end = ;
}
};
node* root;
char s[],ss[];
void insert()
{
int i,l = strlen(s);
node* k = root;
for(i = ;i<l;i++)
{
int id = s[i]-'a';
if(k->next[id] == NULL)
k->next[id] = new node();
k = k->next[id];
}
k->end++;
}
void build()
{
queue<node*> q;
for(int i = ;i<;i++)
{
node* k = root;
if(k->next[i] != NULL)
{
k->next[i]->fail = root;
q.push(k->next[i]);
}
}
while(!q.empty())
{
node*k = q.front();
q.pop();
for(int i = ;i<;i++)
{
if(k->next[i]!=NULL)
{
node*t = k->fail;
while(t!=root&&t->next[i] == NULL) t = t->fail;
if(t->next[i] != NULL) t = t->next[i];
k->next[i]->fail = t;
q.push(k->next[i]);
}
}
}
}
int ask()
{
int i,l = strlen(ss),ans = ;
node *k = root;
for(i = ;i<l;i++)
{
int id = ss[i]-'a';
while(k!=root&&k->next[id] == NULL) k = k->fail;
if(k->next[id]!=NULL) k = k->next[id];
node* t = k;
while(t!=root)
{
ans += t->end;
t->end = ;
t = t->fail;
}
}
return ans;
} int main()
{
int z;
int n,i,j,k;
cin>>z;
while(z--)
{
root = new node();
scanf("%d",&n);
while(n--)
{
scanf("%s",s);
insert();
}
build();
scanf("%s",ss);
printf("%d\n",ask());
}
return ;
}

hdu2222Keywords Search的更多相关文章

  1. hdu2222Keywords Search &lpar;特里&rpar;

    Problem Description In the modern time, Search engine came into the life of everybody like Google, B ...

  2. 【hdu2222-Keywords Search】AC自动机基础裸题

    http://acm.hust.edu.cn/vjudge/problem/16403 题意:给定n个单词,一个字符串,问字符串中出现了多少个单词.(若单词her,he,字符串aher中出现了两个单词 ...

  3. hdu2222Keywords Search字典树入门……

    #include<iostream> #include<cstring> using namespace std; struct node { int num; node *n ...

  4. hdu2222--Keywords Search&plus;AC自己主动机模板

    题目链接:pid=2222">点击进入 KMP对模式串进行处理.然后就能够方便的推断模式串是否在目标串中出现了:这显示适合一个模式串多个目标串的情况.可是假设模式串有多个,这时假设还用 ...

  5. HDU2222Keywords Search AC&lowbar;自动机

    http://blog.csdn.net/niushuai666/article/details/7002823 #include <iostream> #include <cstd ...

  6. &lbrack;数据结构&rsqb;——二叉树(Binary Tree)、二叉搜索树(Binary Search Tree)及其衍生算法

    二叉树(Binary Tree)是最简单的树形数据结构,然而却十分精妙.其衍生出各种算法,以致于占据了数据结构的半壁*.STL中大名顶顶的关联容器--集合(set).映射(map)便是使用二叉树实现 ...

  7. Leetcode 笔记 99 - Recover Binary Search Tree

    题目链接:Recover Binary Search Tree | LeetCode OJ Two elements of a binary search tree (BST) are swapped ...

  8. Leetcode 笔记 98 - Validate Binary Search Tree

    题目链接:Validate Binary Search Tree | LeetCode OJ Given a binary tree, determine if it is a valid binar ...

  9. 基于WebGL 的3D呈现A&ast; Search Algorithm

    http://www.hightopo.com/demo/astar/astar.html 最近搞个游戏遇到最短路径的常规游戏问题,一时起兴基于HT for Web写了个A*算法的WebGL 3D呈现 ...

随机推荐

  1. &lbrack;译&rsqb;:Xamarin&period;Android平台功能——位置服务

    返回索引目录 原文链接:Location Services. 译文链接:Xamarin.Android平台功能--位置服务 本部分介绍位置服务以及与如何使用位置提供商服务 Location Servi ...

  2. 大数据系列(3)——Hadoop集群完全分布式坏境搭建

    前言 上一篇我们讲解了Hadoop单节点的安装,并且已经通过VMware安装了一台CentOS 6.8的Linux系统,咱们本篇的目标就是要配置一个真正的完全分布式的Hadoop集群,闲言少叙,进入本 ...

  3. JavaScript Canvas 根据像素点取位置

    <html> <body> <canvas id="canvas" width="100" height="100&qu ...

  4. Jenkins的Windows Slave的配置

    原文:http://www.cnblogs.com/itech/archive/2011/11/09/2243025.html 参考: https://wiki.jenkins-ci.org/disp ...

  5. java向文件写数据的3种方式

    下边列举出了三种向文件中写入数据的方式,当然还有其他方式,帮助自己理解文件写入类的继承关系.类的关系: file->fileoutputstream->outputstreamWriter ...

  6. 用Jekyll在github上写博客

    用Jekyll在github上写博客——<搭建一个免费的,无限流量的Blog>的注脚 本来打算买域名,买空间,用wordpress写博客的.后来问了一个师兄,他说他是用github的空间, ...

  7. Linux运维宝典:最常用的150个命令汇总

    一.线上查询及帮助命令(2个) 二.文件和目录操作命令(18个) 三.查看文件及内容处理命令(21个) 四.文件压缩及解压缩命令(4个) 五.信息显示命令(11个) 六.搜索文件命令(4个) 七.用户 ...

  8. 团队项目第二周spec设计

    本系统针对局域网进行联机聊天.聊天室分为服务器端和和客户端俩部分,服务器端程序主要 负责侦听客户端发来的信息,客户端需要登录到服务器端才可以实现正常的聊天功能. 1.本软件是一款局域网聊天软件,不能进 ...

  9. AnimateWindow类

    using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; usin ...

  10. SSH批量分发管理

    ssh服务认证类型主要有两个: 基于口令的安全验证: 基于口令的安全验证的方式就是大家一直在用的,只要知道服务器的ssh连接账户.口令.IP及开发的端口,默认22,就可以通过ssh客户端登陆到这台远程 ...