• <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浪潮| 久久人人爽人人人人爽AV| 色综合久久中文综合网| 伊人色综合久久天天网| 亚洲国产精品久久久久久| 囯产极品美女高潮无套久久久 | 亚洲AV伊人久久青青草原| 日产精品久久久一区二区| 久久青青草原精品国产不卡| 狠狠色婷婷综合天天久久丁香| 久久这里只精品99re66| 91久久精品国产成人久久| 久久水蜜桃亚洲av无码精品麻豆| 久久精品国产精品亚洲下载| 欧美熟妇另类久久久久久不卡 | 国产精品无码久久四虎| 久久久久久夜精品精品免费啦| 伊人伊成久久人综合网777| 久久国产美女免费观看精品 | 伊人色综合久久天天人守人婷| 国产ww久久久久久久久久| 国产韩国精品一区二区三区久久| 久久综合九色综合网站| 久久香综合精品久久伊人| 女人高潮久久久叫人喷水| 色8激情欧美成人久久综合电| 久久久网中文字幕| 久久久精品国产Sm最大网站| 国产精品成人久久久久三级午夜电影| 久久国产一区二区| 国产三级精品久久| 久久成人国产精品一区二区| 久久久久久国产a免费观看不卡| 国产成人精品久久亚洲高清不卡 | 91久久精品电影| 狠狠色丁香婷婷久久综合五月 |