• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            付翔的專欄
            在鄙視中成長 記錄成長的點滴
            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 付翔 閱讀(319) 評論(0)  編輯 收藏 引用 所屬分類: ACM 數據結構 、c++

            <2010年4月>
            28293031123
            45678910
            11121314151617
            18192021222324
            2526272829301
            2345678

            常用鏈接

            留言簿(2)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            CSDN - 我的blog地址

            博客

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            国产一级做a爰片久久毛片| 18岁日韩内射颜射午夜久久成人| 精品熟女少妇a∨免费久久| 精品国产乱码久久久久久郑州公司 | 天天爽天天狠久久久综合麻豆 | 亚洲精品无码久久一线| 国产成人精品免费久久久久| 国产精品成人99久久久久| 久久久久亚洲av成人网人人软件| 久久精品国产乱子伦| 国产精品青草久久久久福利99| 漂亮人妻被中出中文字幕久久| 少妇人妻88久久中文字幕| 91久久九九无码成人网站| 久久婷婷五月综合成人D啪 | 狠狠色丁香久久婷婷综合图片| 国内精品九九久久久精品| 亚洲精品NV久久久久久久久久 | 久久精品国产福利国产琪琪| 一本一本久久a久久精品综合麻豆| 91精品国产高清91久久久久久| 色综合久久中文字幕综合网| 日本道色综合久久影院| 久久综合狠狠综合久久综合88| 深夜久久AAAAA级毛片免费看| 国产精品99久久精品爆乳| 久久久久久国产精品无码超碰| 欧美伊人久久大香线蕉综合| 久久婷婷五月综合成人D啪| 天天爽天天爽天天片a久久网| 人妻精品久久久久中文字幕69| 久久午夜免费视频| 亚洲第一永久AV网站久久精品男人的天堂AV | 国产激情久久久久久熟女老人| 久久国产一片免费观看| 国产精品免费久久| 国产精品午夜久久| 久久久久成人精品无码| 久久99精品久久久久久齐齐| 精品乱码久久久久久夜夜嗨 | 成人午夜精品无码区久久|