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

            ACM___________________________

            ______________白白の屋
            posts - 182, comments - 102, trackbacks - 0, articles - 0
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            常用鏈接

            留言簿(24)

            隨筆分類(332)

            隨筆檔案(182)

            FRIENDS

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

            MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋    

             

            題目地址:

                 http://acm.hdu.edu.cn/showproblem.php?pid=1251 

            題目描述:

            統計難題

            Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131070/65535 K (Java/Others)
            Total Submission(s): 5025    Accepted Submission(s): 1853


            Problem Description
            Ignatius最近遇到一個難題,老師交給他很多單詞(只有小寫字母組成,不會有重復的單詞出現),現在老師要他統計出以某個字符串為前綴的單詞數量(單詞本身也是自己的前綴).
             

            Input
            輸入數據的第一部分是一張單詞表,每行一個單詞,單詞的長度不超過10,它們代表的是老師交給Ignatius統計的單詞,一個空行代表單詞表的結束.第二部分是一連串的提問,每行一個提問,每個提問都是一個字符串.

            注意:本題只有一組測試數據,處理到文件結束.
             

            Output
            對于每個提問,給出以該字符串為前綴的單詞的數量.
             

            Sample Input
            banana band bee absolute acm ba b band abc
             

            Sample Output
            2 3 1 0
             

             

             

            題目分析:

                剛學字典樹 ,也就是 trie 樹, 教程很容易看明白, 1251 是一道很明顯的 模板題, 看過 PPT 后 直接敲代碼 1A.

            第一次做, 順便介紹下 trie樹 :

            字典樹(Trie)是一種用于快速字符串檢索的多叉樹結構。其原理是利用字符串的公共前綴來降低時空開銷,從而達到提高程序效率的目的。

              它有如下簡單的性質:

                (1) 根節點不包含字符信息;

                (3) 一棵m度的Trie或者為空,或者由m棵m度的Trie組成。

               搜索字典項目的方法為:

                (1) 從根結點開始一次搜索;

                (2) 取得要查找關鍵詞的第一個字母,并根據該字母選擇對應的子樹      并轉到該子樹繼續進行檢索;

                (3) 在相應的子樹上,取得要查找關鍵詞的第二個字母,

                  并進一步選擇對應的子樹進行檢索。

                (4) 迭代過程……

                (5) 在某個結點處,關鍵詞的所有字母已被取出,則讀取

                  附在該結點上的信息,即完成查找。

            代碼如下 :

                當然也可以拿來做模板 ,    

             /*

            MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋

                      http://www.cnblog.com/MiYu

            Author By : MiYu

            Test      : 1

            Program   : 1251

            */


            #include <iostream>

            using namespace std;

            typedef struct dict DIC;

            struct dict {

                   dict (){ n = 0; memset ( child , 0 , sizeof ( child ) ); }

                   void insert ( char *ins )

                   {

                        DIC *cur = this,*now;

                        int len = strlen ( ins );

                        if ( len == 0 )  return ;

                        for ( int i = 0; i != len; ++ i )

                        {

                              if ( cur->child[ ins[i] - 'a' ] != NULL ) 

                              {

                                   cur = cur->child[ ins[i] - 'a' ];

                                   cur->n ++; 

                              }

                              else

                              {

                                   now = new DIC;

                                   cur->child[ ins[i] - 'a' ] = now;

                                   now->n ++;

                                   cur = now;

                              }

                        } 

                   }

                   int find ( char *ins )

                   {

                        DIC *cur = this;

                        int len = strlen ( ins );

                        if ( 0 == len )  return 0;

                        for ( int i = 0; i != len; ++ i )

                        {

                             if ( cur->child[ ins[i] - 'a' ] != NULL )

                                  cur = cur->child[ ins[i] - 'a' ];  

                             else

                                  return 0; 

                        } 

                        return cur->n;

                   }

            private:

                   DIC *child[26];

                   int n; 

            };

            char word[11];

            int main ()

            {

                DIC dict;

                while ( gets ( word ), strcmp ( word, "") != 0 )

                      dict.insert ( word );

                char qur[11];

                while ( scanf ( "%s",qur ) != EOF )

                {

                      printf ( "%d\n",dict.find ( qur ) ); 

                }    

                return 0;

            }


             

             

            色狠狠久久AV五月综合| 中文字幕亚洲综合久久2| 波多野结衣久久精品| 久久久久久久久无码精品亚洲日韩| 欧美亚洲色综久久精品国产| 久久精品国产福利国产秒| 人人狠狠综合88综合久久| 久久综合国产乱子伦精品免费| 国产亚州精品女人久久久久久 | 老司机国内精品久久久久| 国产亚洲成人久久| 精品久久久噜噜噜久久久| 久久久久国产成人精品亚洲午夜| 日日噜噜夜夜狠狠久久丁香五月| 精品久久久久久无码国产 | 久久精品国产精品青草app| 久久嫩草影院免费看夜色| 蜜臀久久99精品久久久久久小说 | 亚洲中文字幕无码久久2017| 99久久www免费人成精品 | 亚洲午夜久久久久妓女影院 | 性做久久久久久久久| 狠狠色综合网站久久久久久久| 久久精品www人人爽人人| 精品综合久久久久久97| 午夜精品久久久久久| 久久国产精品偷99| 99精品久久久久久久婷婷| 青青国产成人久久91网| 99久久中文字幕| 国产精品久久久久9999| 久久综合精品国产二区无码| 色综合久久久久久久久五月| 人妻丰满?V无码久久不卡| 青春久久| 久久久久久久久久久| 伊人久久无码中文字幕| 亚洲女久久久噜噜噜熟女| 麻豆AV一区二区三区久久| 久久久久成人精品无码中文字幕| 久久亚洲美女精品国产精品|