有道搜索框

迷南。 2022-05-16 10:36 163阅读 0赞

这一题我第一眼看到就觉得应该是用构架良好的二叉搜索树，后来朋友告诉我直接暴力就可以了，让我汗……  
不过我还是用红黑树来做了，后来据了解类似的题目貌似应该用Trie Tree：  
\#include <iostream> \#include <cstdio> \#include <cstring> \#include <cmath> \#include <cstdlib> \#include <string> \#include <vector> \#include <deque> \#include <list> \#include <stack> \#include <queue> \#include <bitset> \#include <set> \#include <map> \#include <algorithm> using namespace std; class classcomp\{ public: bool operator() (string l, string r)\{ return strcmp(l.data(), r.data()) < 0; \} \}; int main()\{ set<string, classcomp> dict; set<string, classcomp>::iterator it; string qword; int n, q, cnt, found; cin >> n; while(n--)\{ cin >> qword; dict.insert(qword); \} cin >> q; while(q--)\{ cnt = 0; cin >> qword; for(it = dict.lower\_bound(qword); it!=dict.end(); ++it)\{ found = (\*it).find(qword); if(found == string::npos || found) break; else\{ if(!cnt)\{ cout << \*it; \}else\{ cout << ' ' << \*it; \} \} ++cnt; if(8 == cnt) break; \} if(!cnt) cout << qword; cout << endl; \} return 0; \}  
  
  
描述 在有道搜索框中，当输入一个或者多个字符时，搜索框会出现一定数量的提示，如下图所示：  
![suggest.jpg][]  
  
现在给你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

[suggest.jpg]: http://poj.youdao.com/groups/youdao/suggest.jpg