昨天断网 博客没有写全 呵呵
- 时间限制:
- 1000ms
- 内存限制:
- 131072kB
- 描述
- 在有道搜索框中，当输入一个或者多个字符时，搜索框会出现一定数量的提示，如下图所示：
现在给你N个单词和一些查询，请输出提示结果，为了简化这个问题，只需要输出以查询词为前缀的并且按字典序排列的最前面的8个单词，如果符合要求的单词一个也没有请只输出当前查询词。 - 输入
- 第一行是一个正整数N，表示词表中有N个单词。
接下来有N行，每行都有一个单词，注意词表中的单词可能有重复，请忽略掉重复单词。所有的单词都由小写字母组成。
接下来的一行有一个正整数Q，表示接下来有Q个查询。
接下来Q行，每行有一个单词，表示一个查询词，所有的查询词也都是由小写字母组成，并且所有的单词以及查询的长度都不超过20，且都不为空
其中：N<=10000,Q<=10000 - 输出
- 对于每个查询，输出一行，按顺序输出该查询词的提示结果，用空格隔开。
- 样例输入
-
10
a
ab
hello
that
those
dict
youdao
world
your
dictionary
6
bob
d
dict
dicti
yo
z
- 样例输出
-
bob
dict dictionary
dict dictionary
dictionary
youdao your
z
用的是trie 树
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
/*
*
*/
struct node{
int next[26];// 对于某一层而言 next【i】 中i就表示该层有的字符了 next【i】的值指向他所指向的结构
int flag;// 用来标记节点有没有被使用
}trie[210000];
char str[100];
char ans[100];
int totle=1;
void insert(){
int p=0;
int k=0;
while(str[k]){
int v=str[k]-'a';
if(trie[p].next[v]==-1)trie[p].next[v]=totle++;
p=trie[p].next[v];
k++;
}
trie[p].flag=1;
}
int cur;
void dfs(int k,int p)//此树在组织的时候 就是按字典来排的
{
if(cur>=8)return;
if(trie[p].flag!=-1){
ans[k]=0;
if(cur==0)printf("%s",ans);
else printf(" %s",ans);
cur++;
}
for(int i=0;i<26;i++)
if(trie[p].next[i]!=-1){
ans[k]=i+'a';
dfs(k+1,trie[p].next[i]);
}
return;
}
void find(){
cur=0;
int p=0,k=0;
while(str[k]&&p!=-1)//比如 abc 按根开始 找到匹配 c 第三层的 P
{
p=trie[p].next[str[k]-'a'];
ans[k]=str[k];
k++;
}
if(p==-1)// 没有匹配的 那么直接打印 按题意来
{
printf("%s\n",str);
return;
}
dfs(k,p);//继续搜 str[k]个字符
printf("\n");
}
int main()
{
freopen("in.txt","r",stdin);
vector<string> my;
int n;
memset(trie,-1,sizeof(trie));
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%s",str);
insert();
}
int q;
scanf("%d",&q);
while(q--){
scanf("%s",str);
find();
}
return 0;
}
同时还看到一位牛人 用stl 写的 那个牛叉 也贴上了 以供自己参考
using namespace std;
string ts;
bool issub(const string c)
{
if (ts.length() > c.length()) return false;
return ts == c.substr(0, ts.length());//c字串中要存在ts 返回true
}
typedef vector<string> DIC;
int main()
{
DIC dict;
string str;
size_t dsize, ssize;
cin >> dsize;
dict.reserve(dsize);//确保dict 的容量至少为dsize
for (size_t i = 0; i < dsize; ++i)
{
cin >> str;
dict.push_back(str);
}
std::sort(dict.begin(), dict.end());//排序
dict.erase(std::unique(dict.begin(), dict.end()), dict.end());//去除重复的
cin >> ssize;
for (size_t i = 0; i < ssize; ++i)
{
DIC::iterator iter;
cin >> ts;
bool found = false;
iter = lower_bound(dict.begin(), dict.end(),ts);
//此函数在msdn 的解释为 在dict 中插入ts 最小的位置并维持序列有序
for(size_t j=0;j<8 && iter!=dict.end();++j,++iter)
{
if(issub(*iter)){
cout<<*iter<<" ";
found=true;
}
}
if (!found)
cout << ts;
cout << endl;
}
return 0;
}
posted on 2010-05-30 00:03
付翔 阅读(309)
评论(0) 编辑 收藏 引用 所属分类:
ACM 数据结构 、
c++