hdu 2846 Repository (字典树)
2024-09-01 17:37:49
Repository
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 7233 Accepted Submission(s): 2278
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 7233 Accepted Submission(s): 2278
Problem Description
When you go shopping, you can search in repository for avalible merchandises by the computers and internet. First you give the search system a name about something, then the system responds with the results. Now you are given a lot merchandise names in repository and some queries, and required to simulate the process.
When you go shopping, you can search in repository for avalible merchandises by the computers and internet. First you give the search system a name about something, then the system responds with the results. Now you are given a lot merchandise names in repository and some queries, and required to simulate the process.
Input
There is only one case. First there is an integer P (1<=P<=10000)representing the number of the merchanidse names in the repository. The next P lines each contain a string (it's length isn't beyond 20,and all the letters are lowercase).Then there is an integer Q(1<=Q<=100000) representing the number of the queries. The next Q lines each contains a string(the same limitation as foregoing descriptions) as the searching condition.
There is only one case. First there is an integer P (1<=P<=10000)representing the number of the merchanidse names in the repository. The next P lines each contain a string (it's length isn't beyond 20,and all the letters are lowercase).Then there is an integer Q(1<=Q<=100000) representing the number of the queries. The next Q lines each contains a string(the same limitation as foregoing descriptions) as the searching condition.
Output
For each query, you just output the number of the merchandises, whose names contain the search string as their substrings.
For each query, you just output the number of the merchandises, whose names contain the search string as their substrings.
Sample Input
20
ad
ae
af
ag
ah
ai
aj
ak
al
ads
add
ade
adf
adg
adh
adi
adj
adk
adl
aes
5
b
a
d
ad
s
20
ad
ae
af
ag
ah
ai
aj
ak
al
ads
add
ade
adf
adg
adh
adi
adj
adk
adl
aes
5
b
a
d
ad
s
Sample Output
0
20
11
11
2
0
20
11
11
2
C/C++:
#include <map>
#include <queue>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <climits>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
const int my_max = 1e6 + ; struct node
{
int id, cnt, next[];
}my_node[my_max];
int flag = ; void my_init(int x)
{
for (int i = ; i < ; ++ i)
my_node[x].next[i] = -;
} void my_insert(char *s, int len, int x)
{
int now = ;
for (int i = ; i < len; ++ i)
{
if (my_node[now].next[s[i] - 'a'] == -)
{
my_node[now].next[s[i] - 'a'] = ++ flag;
now = flag;
my_init(flag);
}
else now = my_node[now].next[s[i] - 'a'];
if (my_node[now].id != x) my_node[now].cnt ++;
my_node[now].id = x;
}
} int my_find(char *s)
{
int now = , len = strlen(s);
for (int i = ; i < len; ++ i)
{
if (my_node[now].next[s[i] - 'a'] == -) return ;
now = my_node[now].next[s[i] - 'a'];
}
return my_node[now].cnt;
} int main()
{
int n, len;
scanf("%d", &n);
char s[];
my_init();
while (n --)
{
scanf("%s", s);
len = strlen(s);
for (int i = ; i < len; ++ i)
my_insert(s + i, len - i, n + );
}
scanf("%d", &n);
while (n --)
{
scanf("%s", s);
printf("%d\n", my_find(s));
}
return ;
}
最新文章
- 解决jquery新加入的元素没有绑定事件问题
- 1Z0-053 争议题目解析577
- es5 and es6
- java for 的用法总结
- [转]LINQ之路系列博客导航
- iptables 命令介绍
- PHP 5.6.11 访问SQL Server2008R2
- [网络]远程访问局域网svn服务器[转]
- Catharanthus roseus(长春花碱)的生物合成
- OSG调试信息显示
- EasyUI - Draggable 拖动控件
- redis事务、管道及消息通知探究
- 小梦windows phone 8.1开发:语音朗读
- 洛谷P3627[APOI2009] (讨厌的)抢掠计划
- Servlet--HttpServlet实现doGet和doPost请求的原理
- 集合,ArrayList
- Servlet基本
- 【Python】学习笔记六:循环
- long 与int 比较问题
- 从es中拉取全部数据/大量数据 使用scroll+scan避免深分页