• <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>

            C小加

            厚德 博學 求真 至善 The bright moon and breeze
            posts - 145, comments - 195, trackbacks - 0, articles - 0
              C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理
            以前學數據結構的時候吧字典樹忽視了,導致到現在才學到。
            字典樹是一種樹形的數據結構,插入的復雜度為單詞的平均長度。本題只需要寫一個插入函數就可以了。
            由于過幾天就要省賽了,等到省賽后總結一下字典樹。

            // trietree.cpp : 定義控制臺應用程序的入口點。
            //
            #include<cstdio>
            #include<iostream>
            #include<string.h>

            using namespace std;
            const int num_chars = 26;            //關鍵碼最大位

            int _max;
            char ans[12];

            class Trie
            {
            public:
                Trie();
                Trie(Trie& tr);
                virtual ~Trie();
                //int trie_search(const char* word, char*entry) const;
                bool insert(const char* word);
            protected:
                struct Trie_node   //關鍵碼類型
                {
                    bool isfin;
                    int cnt;                     //關鍵碼當前位數
                    Trie_node* branch[num_chars];   //關鍵碼存放數組
                    Trie_node();
                };
                Trie_node* root;
            };

            Trie::Trie_node::Trie_node()   //結點定義
            {
                isfin = false;
                cnt = 0;
                for(int i = 0; i < num_chars;++i)
                    branch[i] = NULL;
            }

            Trie::Trie():root(NULL)
            {
            }

            Trie::~Trie()
            {
            }



            bool Trie::insert(const char*word)
            {
                int result = 1,position = 0;
                if(root == NULL)
                    root = new Trie_node;
                char char_code;
                Trie_node *location = root;
                while(location != NULL && *word != 0)
                {
                    if(*word >= 'a'&& *word <= 'z')
                        char_code = *word - 'a';
                    if(location->branch[char_code] == NULL)
                        location->branch[char_code] = new Trie_node;
                    location = location->branch[char_code];
                    position++;
                    word++;
                }

                ++location->cnt;
                if(location->cnt>_max)
                {
                    _max=location->cnt;
                    return true;
                }
                else
                return false;
            }


            int main()
            {
                Trie t;
                int n;
                while(scanf("%d",&n)!=EOF)
                {
                    _max=0;
                    char s[12];
                    for(int i=0;i<n;++i)
                    {
                        scanf("%s",s);
                        if(t.insert(s))
                        {
                            strcpy(ans,s);
                        }

                    }
                    printf("%s %d\n",ans,_max);
                }


                return 0;
            }
            久久人人爽人人爽人人片AV麻豆 | 一本久久免费视频| 久久久久波多野结衣高潮| 新狼窝色AV性久久久久久| 狠狠狠色丁香婷婷综合久久五月| 久久99久久无码毛片一区二区| 欧美亚洲日本久久精品| 嫩草伊人久久精品少妇AV| 精品久久久久久无码人妻蜜桃| 中文字幕久久波多野结衣av| 99久久国产综合精品五月天喷水 | 久久精品亚洲日本波多野结衣 | 久久一区二区免费播放| 久久亚洲AV成人出白浆无码国产| 久久综合精品国产一区二区三区 | 伊人久久大香线蕉综合Av| 国産精品久久久久久久| 91久久精一区二区三区大全| 国产69精品久久久久观看软件| 国产精品久久久久乳精品爆| 无码人妻少妇久久中文字幕蜜桃| 久久亚洲av无码精品浪潮| 99久久精品费精品国产| 久久精品成人免费网站| 国内精品久久久人妻中文字幕| 久久久久久精品无码人妻| 久久综合视频网站| 久久婷婷五月综合色奶水99啪| 伊人精品久久久久7777| 久久乐国产精品亚洲综合| 精品久久久久中文字| 久久99精品久久久久久不卡| 久久久久久久尹人综合网亚洲| 国产精品久久久久久影院 | 久久国产精品成人片免费| 漂亮人妻被黑人久久精品| 亚洲国产另类久久久精品| 久久久久久久人妻无码中文字幕爆| 色婷婷综合久久久中文字幕| 久久99精品久久久久子伦| 久久亚洲精品中文字幕三区|