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

            青青草国产精品久久| 精品综合久久久久久98| 亚洲AV无码久久精品蜜桃| 午夜精品久久久久久中宇| 久久午夜无码鲁丝片| 久久国产精品视频| 国产婷婷成人久久Av免费高清| 久久99精品国产99久久| 久久www免费人成看片| 久久亚洲AV成人出白浆无码国产| 久久久噜噜噜久久熟女AA片| 一本久久免费视频| 国产精品午夜久久| 久久777国产线看观看精品| 久久午夜福利电影| 久久久久久久综合日本| 伊人久久久AV老熟妇色| 国内精品综合久久久40p| 久久九九全国免费| 国产A级毛片久久久精品毛片| 国产一区二区精品久久| 99久久精品免费看国产一区二区三区| 久久国产高清字幕中文| 亚洲第一极品精品无码久久| 久久精品国产欧美日韩| 91精品国产91热久久久久福利| 久久青青草原国产精品免费 | 久久亚洲AV无码精品色午夜| 中文字幕精品久久久久人妻| 欧美777精品久久久久网| 久久精品国产99久久无毒不卡| 亚洲欧美一区二区三区久久| 99久久这里只精品国产免费| 国内精品久久久久国产盗摄| 97久久精品人人澡人人爽| 久久精品国产久精国产思思| 久久亚洲私人国产精品vA| 日本欧美久久久久免费播放网| 漂亮人妻被黑人久久精品| 色88久久久久高潮综合影院| 久久亚洲欧美国产精品|