有道难题-有道搜索框

时间：2010-05-30 来源：华南理工大学

描述

在有道搜索框中，当输入一个或者多个字符时，搜索框会出现一定数量的提示，如下图所示：

现在给你N个单词和一些查询，请输出提示结果，为了简化这个问题，只需要输出以查询词为前缀的并且按字典序排列的最前面的8个单词，如果符合要求的单词一个也没有请只输出当前查询词。

输入

第一行是一个正整数N，表示词表中有N个单词。
接下来有N行，每行都有一个单词，注意词表中的单词可能有重复，请忽略掉重复单词。所有的单词都由小写字母组成。
接下来的一行有一个正整数Q，表示接下来有Q个查询。
接下来Q行，每行有一个单词，表示一个查询词，所有的查询词也都是由小写字母组成，并且所有的单词以及查询的长度都不超过20，且都不为空
其中：N<=10000,Q<=10000

输出

对于每个查询，输出一行，按顺序输出该查询词的提示结果，用空格隔开。

样例输入

hello

that

those

dict

youdao

world

your

dictionary

bob

dict

dicti

样例输出

bob

dict dictionary

dictionary

youdao your

代码

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include <memory.h>
using namespace std;
struct trieNode
{
    int next[26];
    bool isWord;
    char word[22];
    trieNode()
    {
        memset(next,-1,sizeof(next));
        isWord=false;
    }
};
int N=200000;
trieNode tt[200000];
int len;
bool first;
int num;
void insert(char * tar,char * w)
{
    trieNode * p= &tt[0];
    int id ;
    while(*tar)
    {
        id=*tar-'a';
        if(p->next[id]==-1)
        {
            p->next[id]=len;
            len++;
        }
        p=&tt[p->next[id]];
        tar++;
    }
    p->isWord=true;
    strcpy(p->word,w);
}
void DFS(int n)
{
    if(num >= 8)
        return ;
    int i;
    trieNode * p= &tt[n];
    if(p->isWord==true)
    {
        if(first)
        {
            printf("%s",p->word);
            first=false;
                num++;
        }
        else
        {
            printf(" %s",p->word);
            num++;
        }
    }

    for(i=0;i<26;++i)
    {
        if(p->next[i]!=-1)
        {
            DFS(p->next[i]);
        }
    }
}

bool search(char *tar)
{
    trieNode * p= &tt[0];
    int id;
    int n;
    while (* tar)
    {
        id=*tar -'a';
        if(p->next[id]==-1)
            return false;
        n=p->next[id];
        p=&tt[p->next[id]];

        tar++;
    }
    DFS(n);
    return true;
}
int main()
{
    int n,q;
    int i;
    char str[25];
    bool b;
    len=1;
    scanf("%d",&n);
    for(i=0;i<n;++i)
    {
        scanf("%s",&str);
        insert(str,str);
    }
    scanf("%d",&q);
    for(i=0;i<q;++i)
    {
        b=true;
        first=true;
        num=0;
        scanf("%s",&str);
        b=search(str);

        if(b==false)
            printf("%s\n",str);
        else
            printf("\n");
    }
    return 0;
}