昨天斷網 博客沒有寫全 呵呵
- 時間限制:
- 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
付翔 閱讀(319)
評論(0) 編輯 收藏 引用 所屬分類:
ACM 數據結構 、
c++