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

            }


             

             

            欧美久久综合性欧美| 草草久久久无码国产专区| 久久影院亚洲一区| 亚洲精品tv久久久久| 久久国产热精品波多野结衣AV| 久久亚洲精精品中文字幕| 一级做a爰片久久毛片人呢| 久久久久久午夜精品| 久久这里只有精品18| 久久久噜噜噜久久中文字幕色伊伊| 一日本道伊人久久综合影| 国产成人精品久久二区二区| 久久免费国产精品| 精品国产一区二区三区久久| 精品国产乱码久久久久软件| 麻豆精品久久久一区二区| 囯产精品久久久久久久久蜜桃| 大蕉久久伊人中文字幕| 伊人久久大香线蕉综合影院首页 | 国产—久久香蕉国产线看观看| 四虎影视久久久免费观看| 久久99国产精品久久| 久久久久精品国产亚洲AV无码| 国产AV影片久久久久久| 久久久久亚洲精品天堂| 青青草原综合久久大伊人| 欧美色综合久久久久久| 国产精品狼人久久久久影院| 久久精品国产第一区二区三区| 久久精品国产2020| 伊人 久久 精品| 少妇被又大又粗又爽毛片久久黑人 | 久久九九全国免费| 少妇精品久久久一区二区三区| 欧美久久一区二区三区| 久久九色综合九色99伊人| 久久99毛片免费观看不卡| 97精品伊人久久大香线蕉app| 亚洲精品白浆高清久久久久久 | 久久综合给合久久国产免费| 久久久久久毛片免费播放|