• <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
            <2010年8月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿(24)

            隨筆分類(332)

            隨筆檔案(182)

            FRIENDS

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

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

             

            題目地址 :

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

            題目描述:

            Hat’s Words

            Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
            Total Submission(s): 1384    Accepted Submission(s): 506


            Problem Description
            A hat’s word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary.
            You are to find all the hat’s words in a dictionary.
             

            Input
            Standard input consists of a number of lowercase words, one per line, in alphabetical order. There will be no more than 50,000 words.
            Only one case.
             

            Output
            Your output should contain all the hat’s words, one per line, in alphabetical order.
             

            Sample Input
            a ahat hat hatword hziee word
             

            Sample Output
            ahat hatword
             

            題目分析 :

              

                    字典樹的題目, 這個題的方法比較暴力,  在輸入的時候將每個單詞都加入字典樹,  并用數組將所有的串都存起來來.

            在輸入完成后,  對每個單詞進行拆分, 也就是暴力枚舉單詞不同位置的前后部分, 看在字典樹中是否存在, 存在即輸出.

            不過貌似數據比較弱, 說是按字典順序輸出, 但其實他的輸入本就是按字典順序輸入的, 所以將排序也面了 , 呵呵.

                另外,其實這題用STL 做更簡單, 當然追求效率除外.

            trie 代碼:

             /*

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

                      http://www.cnblog.com/MiYu

            Author By : MiYu

            Test      : 1

            Program   : 1247

            */


            #include <iostream>

            #include <algorithm>

            #include <string>

            using namespace std;

            typedef struct dictor DIC;

            DIC *root = NULL;

            struct dictor {

                   dictor (){ exist = false; memset ( child , 0 , sizeof ( child ) ); }

                   void insert ( char *ins );

                   bool find ( const char *ins );

            private:

                   DIC *child[26];

                   bool exist; 

            };

            void dictor::insert ( char *ins )

            {

                        DIC *cur = root,*now;

                        int len = strlen ( ins );

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

                        {

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

                              {

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

                              }

                              else

                              {

                                   now = new DIC;

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

                                   cur = now;

                              }

                        } 

                        cur->exist = true;

            }

            bool dictor::find ( const char *ins )

            {

                        DIC *cur = root;

                        int len = strlen ( ins );

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

                        {

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

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

                             else

                                  return false; 

                        } 

                        return cur->exist;

            }

            char words[50050][100];

            char s1[100],s2[100];

            DIC dict;

            int main ()

            {

                root = &dict;

                int n = 0;

                while ( scanf ( "%s",words[n] ) != EOF )

                {

                        dict.insert ( words[n++] );

                }

                for ( int i = 0; i < n; ++ i )

                {

                      int len = strlen ( words[i] );

                      for ( int j = 1; j < len; ++ j )

                      {

                            memset ( s1, 0, sizeof ( s1 ) );

                            memset ( s2, 0, sizeof ( s2 ) );

                            strncpy ( s1, words[i], j );

                            strcpy ( s2, words[i]+j );

                            if ( dict.find ( s1 ) && dict.find ( s2 ) )

                            {

                                 printf ( "%s\n", words[i] );

                                 break; 

                            }

                      }  

                }  

                //system ( "pause" );

                return 0;

            }


            STL  代碼 :

             

             /*

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

                      http://www.cnblog.com/MiYu

            Author By : MiYu

            Test      : 2

            Program   : 1247

            */


            #include <iostream>

            #include <string>

            #include <map>

            using namespace std;

            map < string , int > mp;

            string str[50005];

            int main ()

            {

                int n = 0;

                while ( cin >> str[n] ) mp[ str[n++] ] = 1;

                for ( int i = 0; i < n; ++ i )

                {

                      unsigned len = str[i].size ();

                      for ( unsigned j = 1; j < len; ++ j )

                      {

                           string s1 ( str[i], 0, j );

                           string s2 ( str[i], j );

                           if ( mp[s1] == 1 && mp[s2] == 1 )

                           {

                                cout << str[i] << endl; 

                                break;

                           }

                      } 

                }

                return 0;

            }


             

             

            欧美亚洲国产精品久久| 88久久精品无码一区二区毛片| 久久九九久精品国产免费直播| 久久99精品免费一区二区| 麻豆av久久av盛宴av| 国产精品欧美久久久天天影视 | 久久国产成人精品国产成人亚洲| 青青青国产成人久久111网站| 久久亚洲国产成人影院| 国产精品一区二区久久不卡| 欧美午夜A∨大片久久| 久久久女人与动物群交毛片 | 伊人色综合久久| 97精品依人久久久大香线蕉97 | 国产精品久久久久蜜芽| 99久久国产综合精品麻豆| 怡红院日本一道日本久久 | 久久精品中文闷骚内射| 久久精品无码一区二区app| 久久久国产乱子伦精品作者| 久久亚洲高清综合| 久久免费线看线看| 精品国产乱码久久久久久1区2区| 亚洲精品97久久中文字幕无码| 久久国产高清字幕中文| 久久精品国产亚洲AV蜜臀色欲| 久久久久九国产精品| 97精品伊人久久久大香线蕉| 久久国产精品无码一区二区三区 | 狠狠色婷婷久久一区二区| 麻豆久久| 伊人久久大香线蕉综合5g| 狠狠色丁香婷婷综合久久来来去 | 久久久久99精品成人片三人毛片| 国产精品99久久久久久人| 久久久久亚洲AV无码专区体验| 久久久久亚洲AV无码观看| 久久夜色撩人精品国产小说| 久久久国产精品| 午夜精品久久久内射近拍高清 | 伊人久久五月天|