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

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>
            欧美国产亚洲视频| 老牛国产精品一区的观看方式| 欧美国产免费| 99精品国产在热久久婷婷| 亚洲国产精品传媒在线观看 | 亚洲在线不卡| 国产日韩欧美| 欧美丰满少妇xxxbbb| 欧美日本精品| 亚洲欧美中文日韩v在线观看| 亚洲欧美国产高清va在线播| 国产主播一区二区三区四区| 欧美国产日本韩| 国产精品初高中精品久久| 欧美在线免费视屏| 卡一卡二国产精品| 国产精品99久久久久久www| 性欧美暴力猛交69hd| 亚洲精品黄网在线观看| 亚洲欧美国产一区二区三区| 亚洲福利视频在线| 亚洲深夜影院| 最新高清无码专区| 亚洲欧美日韩中文在线制服| 亚洲国产欧美一区| 欧美一区二区三区在线看| 亚洲精品一二三区| 欧美在线视频不卡| 一区二区日韩欧美| 久久久久免费| 亚洲淫片在线视频| 欧美大色视频| 久久视频一区二区| 国产精品美女久久| 亚洲欧洲偷拍精品| 激情丁香综合| 亚洲性感激情| 欧美在线观看天堂一区二区三区| 亚洲精品国产精品乱码不99按摩| 亚洲欧美激情一区| 这里只有精品视频| 免费h精品视频在线播放| 欧美一级在线视频| 欧美三级视频在线| 亚洲激情网址| 亚洲国产视频直播| 久久久久久亚洲精品杨幂换脸| 午夜精品一区二区三区在线播放| 欧美激情精品久久久久久蜜臀 | 小黄鸭精品密入口导航| 欧美日韩在线高清| 最新日韩av| 亚洲每日在线| 免费在线观看一区二区| 毛片基地黄久久久久久天堂| 国产欧美日韩亚州综合| 亚洲一区精品视频| 午夜亚洲伦理| 国产伦理一区| 亚洲综合99| 欧美在线观看www| 国产精品视频久久久| 亚洲一区二区高清| 欧美专区中文字幕| 国产在线日韩| 久久男人资源视频| 欧美成人精品高清在线播放| 亚洲第一页在线| 免费观看久久久4p| 亚洲精品久久久久| 在线视频亚洲一区| 国产精品扒开腿做爽爽爽视频 | 久久精品国产在热久久| 久久综合五月天婷婷伊人| 在线观看久久av| 欧美大片免费观看| 在线视频精品一区| 欧美一区二区三区视频| 国产一区视频网站| 久久综合五月| 亚洲精品免费看| 香蕉久久夜色精品国产| 中日韩视频在线观看| 午夜日韩在线| 狠狠综合久久av一区二区小说| 久久视频精品在线| 亚洲日本成人| 欧美一区二区三区四区在线| 红桃视频欧美| 欧美久久久久久蜜桃| 亚洲一区二区免费在线| 米奇777超碰欧美日韩亚洲| 亚洲日韩成人| 国产精品主播| 欧美高清在线精品一区| 亚洲欧美变态国产另类| 蜜臀va亚洲va欧美va天堂| 日韩一级裸体免费视频| 国产日韩综合| 欧美日韩国产精品一卡| 欧美一区影院| 亚洲精品视频在线| 久久久久久亚洲精品中文字幕| 亚洲精品一区二区三区不| 国产精品影院在线观看| 免费观看不卡av| 性欧美1819性猛交| 亚洲精品三级| 免费不卡中文字幕视频| 午夜精品免费视频| 亚洲精品免费一二三区| 国产一区日韩一区| 国产精品成人一区二区三区夜夜夜| 久久久精品视频成人| 亚洲午夜av在线| 最新亚洲激情| 欧美成人tv| 久久久精品免费视频| 亚洲一区二区三区视频| 亚洲欧洲精品一区二区三区 | 老司机免费视频一区二区| 亚洲深夜福利在线| 亚洲茄子视频| 亚洲国产精品成人精品| 国产又爽又黄的激情精品视频| 欧美日韩中文字幕在线| 欧美精品性视频| 美女图片一区二区| 久久夜色精品国产欧美乱| 亚洲欧美日韩一区二区在线| 在线午夜精品| 在线一区免费观看| 一本色道久久88综合日韩精品| 亚洲激情二区| 亚洲精品日韩激情在线电影| 亚洲国产91精品在线观看| 欧美 日韩 国产 一区| 老牛嫩草一区二区三区日本| 久久精品在线播放| 久久青草欧美一区二区三区| 欧美影院成年免费版| 欧美中在线观看| 久久精品亚洲一区二区| 久久精品72免费观看| 久久久久成人精品| 久久久久久久久久久一区 | 久久综合婷婷| 欧美肥婆在线| 亚洲毛片在线看| 亚洲国产另类精品专区 | 欧美精品免费视频| 欧美日韩国产一区精品一区| 欧美—级a级欧美特级ar全黄| 欧美激情视频一区二区三区在线播放 | 欧美va亚洲va日韩∨a综合色| 国产一区在线观看视频| 在线观看亚洲视频啊啊啊啊| 国产精品99一区二区| 国产精品一区二区久久精品| 国产精品一区二区你懂得| 国产亚洲精品bt天堂精选| 韩国v欧美v日本v亚洲v| 亚洲青色在线| 亚洲一区视频| 久久偷看各类wc女厕嘘嘘偷窃| 欧美国产在线电影| 一区二区av在线| 久久精品成人欧美大片古装| 男人的天堂亚洲在线| 欧美三区视频| 狠狠色综合一区二区| 99精品欧美一区| 久久精品日产第一区二区三区| 蜜月aⅴ免费一区二区三区| 亚洲人在线视频| 先锋影音久久久| 欧美jjzz| 国产亚洲精品高潮| 日韩午夜电影在线观看| 欧美一区2区三区4区公司二百| 媚黑女一区二区| 亚洲一区二区高清| 欧美丰满高潮xxxx喷水动漫| 国产免费一区二区三区香蕉精| 亚洲国产小视频| 久久精品欧洲| 一本色道久久综合| 女同一区二区| 韩国成人福利片在线播放| 一区二区精品国产| 欧美大片第1页| 亚洲欧美在线aaa| 欧美日韩美女在线| 亚洲激情小视频| 久久嫩草精品久久久精品一 | 亚洲无限av看| 亚洲福利av| 久久久一二三| 国产亚洲激情在线| 午夜精品久久久久久99热软件|