付翔的专栏
在鄙视中成长 记录成长的点滴
posts - 106,  comments - 32,  trackbacks - 0
昨天断网 博客没有写全 呵呵

时间限制: 
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 付翔 阅读(296) 评论(0)  编辑 收藏 引用 所属分类: ACM 数据结构c++

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2010年5月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

常用链接

留言簿(2)

随笔分类

随笔档案

文章分类

文章档案

CSDN - 我的blog地址

博客

搜索

  •  

最新评论

阅读排行榜

评论排行榜