昨天斷網(wǎng) 博客沒有寫全 呵呵
- 時(shí)間限制:
- 1000ms
- 內(nèi)存限制:
- 131072kB
- 描述
- 在有道搜索框中，當(dāng)輸入一個(gè)或者多個(gè)字符時(shí)，搜索框會(huì)出現(xiàn)一定數(shù)量的提示，如下圖所示：
現(xiàn)在給你N個(gè)單詞和一些查詢，請(qǐng)輸出提示結(jié)果，為了簡化這個(gè)問題，只需要輸出以查詢?cè)~為前綴的并且按字典序排列的最前面的8個(gè)單詞，如果符合要求的單詞一個(gè)也沒有請(qǐng)只輸出當(dāng)前查詢?cè)~。 - 輸入
- 第一行是一個(gè)正整數(shù)N，表示詞表中有N個(gè)單詞。
接下來有N行，每行都有一個(gè)單詞，注意詞表中的單詞可能有重復(fù)，請(qǐng)忽略掉重復(fù)單詞。所有的單詞都由小寫字母組成。
接下來的一行有一個(gè)正整數(shù)Q，表示接下來有Q個(gè)查詢。
接下來Q行，每行有一個(gè)單詞，表示一個(gè)查詢?cè)~，所有的查詢?cè)~也都是由小寫字母組成，并且所有的單詞以及查詢的長度都不超過20，且都不為空
其中：N<=10000,Q<=10000 - 輸出
- 對(duì)于每個(gè)查詢，輸出一行，按順序輸出該查詢?cè)~的提示結(jié)果，用空格隔開。
- 樣例輸入
-
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];// 對(duì)于某一層而言 next【i】 中i就表示該層有的字符了 next【i】的值指向他所指向的結(jié)構(gòu)
int flag;// 用來標(biāo)記節(jié)點(diǎn)有沒有被使用
}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)//此樹在組織的時(shí)候 就是按字典來排的
{
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);//繼續(xù)搜 str[k]個(gè)字符
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;
}
同時(shí)還看到一位牛人 用stl 寫的 那個(gè)牛叉 也貼上了 以供自己參考
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());//去除重復(fù)的
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);
//此函數(shù)在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;
}