青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            亚洲欧美日本在线| 亚洲精品综合在线| 久久久国产精品一区二区中文| 一区二区三区.www| 国产精品日韩专区| 久久精品官网| 蜜桃伊人久久| 亚洲午夜久久久| 午夜精品电影| …久久精品99久久香蕉国产| 亚洲国产cao| 欧美粗暴jizz性欧美20| 欧美福利影院| 欧美伊人久久大香线蕉综合69| 欧美在线亚洲在线| 日韩视频在线永久播放| 亚洲亚洲精品在线观看| 亚洲高清久久久| 这里只有精品电影| 国语自产精品视频在线看8查询8| 欧美电影资源| 国产精品久久久久久亚洲调教 | 欧美国产亚洲视频| 亚洲欧美日韩精品久久久| 久久久久久999| 亚洲一区二区视频在线| 久久欧美中文字幕| 午夜老司机精品| 欧美高潮视频| 久久伊人亚洲| 国产精品久久久久久久7电影| 蜜桃久久av| 国产精品永久免费观看| 91久久精品视频| 伊人久久噜噜噜躁狠狠躁| 亚洲少妇一区| 一区二区三区你懂的| 久久一区二区三区国产精品| 性欧美1819sex性高清| 欧美电影免费观看大全| 久久综合国产精品台湾中文娱乐网| 欧美美女bb生活片| 欧美国产另类| 一区二区三区中文在线观看 | 久久精品国产一区二区电影| 欧美精品一区二区视频| 美女视频黄免费的久久| 国产一区二区三区四区hd| 一本色道久久综合亚洲精品高清| 亚洲国产日韩在线一区模特| 久久性色av| 美女脱光内衣内裤视频久久网站| 国产精品永久免费视频| 亚洲图片欧洲图片日韩av| 一本色道久久精品| 欧美欧美在线| 亚洲精品无人区| 一区二区欧美激情| 欧美伦理影院| 9色porny自拍视频一区二区| 在线视频欧美一区| 欧美三级日韩三级国产三级| 99国产精品视频免费观看| 在线视频一区观看| 欧美偷拍一区二区| 亚洲视频免费在线观看| 性色av一区二区三区在线观看 | 欧美性大战久久久久久久蜜臀| 亚洲精品麻豆| 亚洲自拍偷拍一区| 国产欧美日韩亚州综合| 日韩午夜中文字幕| 欧美日韩国产一区二区三区| 在线亚洲成人| 久久久久久穴| 最新成人在线| 欧美日韩一区二区三区在线观看免 | 欧美大片免费久久精品三p| 在线欧美视频| 欧美精品18+| 亚洲无线观看| 老司机午夜免费精品视频| 亚洲高清精品中出| 欧美三级乱码| 久久se精品一区精品二区| 女同性一区二区三区人了人一| 最新中文字幕一区二区三区| 欧美日韩在线播放三区四区| 亚洲自拍电影| 欧美二区乱c少妇| 亚洲视频欧美在线| 韩国成人福利片在线播放| 麻豆精品一区二区av白丝在线| 亚洲人被黑人高潮完整版| 欧美一区二区三区男人的天堂| 黄色成人在线免费| 欧美日韩在线看| 久久精品五月婷婷| 亚洲精品国产精品乱码不99 | 男女激情久久| 亚洲主播在线播放| 亚洲国产婷婷香蕉久久久久久99| 国产精品国产三级国产aⅴ无密码| 久久久91精品国产一区二区精品| 亚洲日本精品国产第一区| 欧美一级艳片视频免费观看| 最新国产成人在线观看| 国产精品色一区二区三区| 欧美电影电视剧在线观看| 午夜精品999| 一区二区欧美精品| 欧美国产高清| 久久精品青青大伊人av| 99精品视频免费全部在线| 狠狠色噜噜狠狠色综合久| 欧美日韩亚洲激情| 欧美电影免费观看网站| 欧美主播一区二区三区| 亚洲视频在线一区| 亚洲欧洲在线一区| 欧美1区2区视频| 久久久久一本一区二区青青蜜月| 亚洲视频专区在线| 亚洲精品视频免费观看| 亚洲电影免费观看高清完整版在线观看 | 久久久一本精品99久久精品66| 一区二区三区.www| 亚洲精品国产欧美| 亚洲第一黄色| 又紧又大又爽精品一区二区| 国产日韩欧美视频| 国产精品视频区| 国产精品第一页第二页第三页| 欧美精品亚洲精品| 欧美精品在线免费播放| 欧美激情女人20p| 欧美91精品| 欧美国产日韩在线| 欧美顶级少妇做爰| 欧美精品一区二| 欧美日韩国产在线| 欧美三级视频| 国产精品私房写真福利视频| 国产精品二区在线| 国产免费成人| 国产一区香蕉久久| 黄色av日韩| 亚洲三级免费电影| 一本大道久久a久久精二百| 一区二区三区欧美视频| 中文高清一区| 午夜久久黄色| 久久一二三国产| 欧美激情1区2区3区| 亚洲黄色免费| 在线亚洲欧美| 欧美一区二区三区四区在线观看地址| 香蕉久久夜色精品国产使用方法 | 亚洲精品欧美日韩专区| 在线亚洲伦理| 欧美在线首页| 欧美精品亚洲二区| 国产精品一区二区三区久久 | 欧美久久成人| 国产欧美日韩综合精品二区| 今天的高清视频免费播放成人| 亚洲国产日韩一区二区| 亚洲一级片在线观看| 久久精品在线观看| 亚洲国语精品自产拍在线观看| 一本色道久久综合亚洲精品婷婷 | 欧美激情视频在线播放| 99这里只有精品| 久久九九国产精品| 欧美日韩成人在线播放| 国产午夜精品美女视频明星a级| 亚洲成人在线免费| 午夜精品久久久久久99热| 欧美本精品男人aⅴ天堂| 一二三区精品| 久久婷婷av| 国产精品亚洲产品| 日韩天堂av| 久久视频这里只有精品| 日韩视频免费观看高清在线视频| 亚洲欧美视频一区二区三区| 欧美大片在线观看一区| 国产日韩欧美在线视频观看| 亚洲美女视频网| 狂野欧美激情性xxxx欧美| 亚洲午夜激情网站| 欧美经典一区二区三区| 1769国产精品| 久久精品成人一区二区三区蜜臀 | 午夜在线一区| 国产精品av久久久久久麻豆网| 亚洲激情网址| 久久综合九色九九| 午夜欧美理论片| 亚洲国产小视频在线观看|