• <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 自動機

            我的代碼:

              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) 評論(0)  編輯 收藏 引用 所屬分類: ACM

            久久久亚洲AV波多野结衣| 亚洲欧美精品一区久久中文字幕 | 久久综合色之久久综合| 久久精品亚洲福利| 久久九九兔免费精品6| 国产高潮国产高潮久久久| 亚洲国产成人久久综合碰碰动漫3d | 72种姿势欧美久久久久大黄蕉| 久久96国产精品久久久| 国产精品久久久久久一区二区三区| 亚洲国产精品热久久| 久久亚洲AV成人无码软件| 国产精品久久国产精品99盘| 久久久久亚洲AV无码专区网站| 久久久女人与动物群交毛片| 国产精品成人99久久久久 | 99久久精品日本一区二区免费| 久久精品国产亚洲5555| 国产成人久久精品一区二区三区 | 99久久99这里只有免费费精品| 久久综合久久鬼色| 精品免费久久久久国产一区| 色偷偷88888欧美精品久久久 | 久久综合香蕉国产蜜臀AV| 久久久精品人妻无码专区不卡| 精品久久久久久中文字幕人妻最新| 日韩美女18网站久久精品| 久久九九全国免费| 国产成人综合久久综合| 久久久久亚洲AV无码专区体验| 亚洲国产精品成人久久蜜臀| 99久久免费只有精品国产| 久久精品国产亚洲av麻豆小说| 99久久香蕉国产线看观香| 婷婷久久综合九色综合九七| 亚洲国产成人久久综合一| 88久久精品无码一区二区毛片| 狠狠色丁香久久婷婷综| 国产美女久久久| 99久久成人18免费网站| 国产—久久香蕉国产线看观看|