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

            coreBugZJ

            此 blog 已棄。

            Keywords Search,HDOJ 2222

            Keywords Search

            Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

            Problem Description
            In the modern time, Search engine came into the life of everybody like Google, Baidu, etc.
            Wiskey also wants to bring this feature to his image retrieval system.
            Every image have a long description, when users type some keywords to find the image, the system will match the keywords with description of image and show the image which the most keywords be matched.
            To simplify the problem, giving you a description of image, and some keywords, you should tell me how many keywords will be match.
             

            Input
            First line will contain one integer means how many cases will follow by.
            Each case will contain two integers N means the number of keywords and N keywords follow. (N <= 10000)
            Each keyword will only contains characters 'a'-'z', and the length will be not longer than 50.
            The last line is the description, and the length will be not longer than 1000000.
             

            Output
            Print how many keywords are contained in the description.
             

            Sample Input
            1
            5
            she
            he
            say
            shr
            her
            yasherhs
             

            Sample Output
            3


            AC 自動(dòng)機(jī)

            我的代碼:

              1 #include <iostream>
              2 #include <cstdio>
              3 
              4 using namespace std;
              5 
              6 const int ACTC = 26;
              7 const int ACTM = 800000;
              8 const int ACQL = 800000;
              9 
             10 struct AC
             11 {
             12         int count;
             13         AC * fail;
             14         AC * ch[ ACTC ];
             15 };
             16 
             17 AC * que[ ACQL ];
             18 
             19 AC * ac_new( bool init = false ) {
             20         int i;
             21         AC * p;
             22         static AC memAC[ ACTM ];
             23         static int tot = 0;
             24         if ( init ) {
             25                 tot = 0;
             26                 return 0;
             27         }
             28         p = memAC + tot++;
             29         p->count = 0;
             30         p->fail  = 0;
             31         for ( i = 0; i < ACTC; ++i )
             32                 p->ch[ i ] = 0;
             33         return p;
             34 }
             35 
             36 int ac_add( AC * & root, const char * first, const char * last ) {
             37         AC ** p = &root;
             38         for ( ; ; ) {
             39                 if ( *== 0 ) *= ac_new();
             40                 if ( first == last ) return ++( (*p)->count );
             41                 p = &( (*p)->ch[ *first++ ] );
             42         }
             43 }
             44 
             45 void ac_build( AC * root ) {
             46         // root != 0
             47         int qh = 0, qt = 1, i;
             48         AC *pf, *pc, *pt;
             49         root->fail = 0;
             50         que[ 0 ] = root;
             51         while ( qh != qt ) {
             52                 pf = que[ qh ];
             53                 qh = ( qh + 1  ) % ACQL;
             54                 for ( i = 0; i < ACTC; ++i ) {
             55                         if ( pc = pf->ch[ i ] ) {
             56                                 for ( pt = pf->fail; pt && ( pt->ch[ i ] == 0 ); pt = pt->fail )
             57                                         ;
             58                                 pc->fail = pt ? pt->ch[ i ] : root;
             59                                 que[ qt ] = pc;
             60                                 qt = ( qt + 1 ) % ACQL;
             61                         }
             62                 }
             63         }
             64 }
             65 
             66 int ac_query( AC * root, const char * first, const char * last ) {
             67         // root != 0
             68         int ans = 0;
             69         AC *= root, *q;
             70         while ( first != last ) {
             71                 while ( p && ( p->ch[ *first ] == 0 ) ) {
             72                         p = p->fail;
             73                 }
             74                 if ( p ) {
             75                         q = p = p->ch[ *first++ ];
             76                         while ( q && ( q->count != -1 ) ) {
             77                                 ans += q->count;
             78                                 q->count = -1;
             79                                 q = q->fail;
             80                         }
             81                 }
             82                 else {
             83                         p = root;
             84                         ++first;
             85                 }
             86         }
             87         return ans;
             88 }
             89 
             90 char txt[ 1000009 ], pat[ 70 ];
             91 AC * root;
             92 
             93 int main() {
             94         int td, n;
             95         char * pc;
             96         scanf( "%d"&td );
             97         while ( td-- ) {
             98                 scanf( "%d%*c"&n );
             99                 ac_new( true );
            100                 root = 0;
            101                 while ( n-- ) {
            102                         gets( pat );
            103                         for ( pc = pat; *pc; ++pc )
            104                                 *pc -= 'a';
            105                         ac_add( root, pat, pc );
            106                 }
            107                 gets( txt );
            108                 for ( pc = txt; *pc; ++pc )
            109                         *pc -= 'a';
            110                 ac_build( root );
            111                 printf( "%d\n", ac_query( root, txt, pc ) );
            112         }
            113         return 0;
            114 }
            115 


            posted on 2011-03-25 17:34 coreBugZJ 閱讀(454) 評(píng)論(0)  編輯 收藏 引用 所屬分類: ACM

            久久笫一福利免费导航| 久久久久无码专区亚洲av| 久久无码高潮喷水| 久久久一本精品99久久精品88| 97久久精品无码一区二区天美| 99久久精品免费看国产一区二区三区| 国产福利电影一区二区三区久久老子无码午夜伦不 | 中文字幕无码久久人妻| 久久久久亚洲av成人网人人软件 | 色综合久久88色综合天天| 色婷婷综合久久久久中文字幕| 久久久久国产精品熟女影院| 激情综合色综合久久综合| 狠狠色丁香婷婷久久综合五月| 亚洲欧美日韩中文久久| 精品多毛少妇人妻AV免费久久| 热久久最新网站获取| 国产精品免费久久久久影院| 亚洲国产精品久久电影欧美 | 亚洲国产精品成人久久| 欧美午夜A∨大片久久| 77777亚洲午夜久久多喷| 无码任你躁久久久久久老妇App| 丁香狠狠色婷婷久久综合| 精品无码久久久久国产动漫3d| 久久人人爽人爽人人爽av| 久久精品国产福利国产秒| 人妻久久久一区二区三区| 蜜桃麻豆WWW久久囤产精品| 久久本道久久综合伊人| 国产福利电影一区二区三区,免费久久久久久久精 | 国产精品综合久久第一页| 99久久免费国产精品热| 久久国产色AV免费观看| 人妻精品久久久久中文字幕一冢本| 久久久久久免费视频| 国内精品久久国产| 97久久国产综合精品女不卡 | 久久久久久国产a免费观看黄色大片| 久久精品视屏| 狠狠色伊人久久精品综合网|