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

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伊人| 老司机一区二区| 亚洲——在线| 久久久国产精品一区二区中文 | 国产精品有限公司| 欧美不卡在线视频| 欧美性猛交xxxx免费看久久久| 久久国产夜色精品鲁鲁99| 免费亚洲电影在线观看| 亚洲一区二区成人在线观看| 久久av一区二区三区漫画| 99re成人精品视频| 久久精品国产精品亚洲精品| 一区二区三区导航| 久久久www| 亚洲欧美视频一区| 欧美黄色aa电影| 久久精视频免费在线久久完整在线看| 欧美韩日一区| 久久中文久久字幕| 国产精品久久网| 亚洲精品久久久久久久久久久久久 | 亚洲毛片播放| 亚洲第一精品夜夜躁人人爽| 亚洲一区二区欧美日韩| 亚洲三级影院| 久久久久久久999| 午夜精品久久久久久久久| 欧美高清在线视频观看不卡| 久久亚洲欧美| 国产午夜精品理论片a级大结局 | 欧美激情视频一区二区三区免费 | 亚洲清纯自拍| 亚洲激情在线| 久久久成人精品| 欧美在线一二三四区| 国产精品白丝黑袜喷水久久久| 欧美激情亚洲另类| 在线免费观看日本欧美| 欧美一级黄色网| 久久国产精品一区二区| 国产精品日本一区二区| 一区二区三区高清在线观看| 一区二区精品国产| 欧美日韩三级| 99v久久综合狠狠综合久久| 亚洲三级电影在线观看| 欧美成人精品激情在线观看| 欧美福利在线| 最新日韩在线视频| 欧美第一黄色网| 亚洲欧洲在线免费| 一区二区高清在线观看| 欧美三区在线观看| 一区二区三区国产精华| 小处雏高清一区二区三区| 国产欧美日韩另类一区| 性色av一区二区三区| 久久久久99| 亚洲激情社区| 欧美日韩a区| 亚洲私拍自拍| 久久亚洲综合网| 91久久国产精品91久久性色| 欧美成人四级电影| 日韩一区二区精品在线观看| 亚洲欧美日韩久久精品 | 欧美成人免费在线视频| 一本久久知道综合久久| 欧美在线观看一区| 亚洲第一视频网站| 欧美日韩国产一区二区三区地区| 一二三区精品福利视频| 久久大逼视频| 亚洲日本黄色| 国产精品永久免费视频| 久久精品国产综合| 亚洲裸体俱乐部裸体舞表演av| 午夜欧美理论片| 亚洲第一中文字幕| 国产精品v欧美精品∨日韩| 久久aⅴ国产紧身牛仔裤| 亚洲人成在线影院| 久久久av网站| 国产精品99久久99久久久二8| 国产日韩欧美一二三区| 欧美高清影院| 欧美影院精品一区| 亚洲美女电影在线| 六月婷婷一区| 亚洲欧美视频在线观看视频| 亚洲激情影视| 国精品一区二区| 欧美三级在线| 欧美 日韩 国产在线| 亚洲视频电影图片偷拍一区| 欧美成年网站| 久久精品二区亚洲w码| 日韩午夜av在线| 国内自拍亚洲| 国产精品天美传媒入口| 欧美.日韩.国产.一区.二区| 西瓜成人精品人成网站| 一区二区三区高清在线观看| 欧美激情一区二区三区蜜桃视频| 欧美一区二区视频97| 亚洲一级高清| 日韩午夜高潮| 亚洲日本理论电影| 亚洲高清在线观看| 狠狠色狠狠色综合| 国产日本精品| 国产精品久久久久久超碰| 欧美精品一区二区精品网| 久久精品五月婷婷| 欧美一区二区三区精品| 亚洲免费网址| 亚洲综合社区| 先锋影音久久久| 亚洲欧美日韩专区| 亚洲欧美日韩国产中文在线| 亚洲一区二区三区在线视频| 99在线热播精品免费| 亚洲裸体在线观看| 99热这里只有精品8| 亚洲美女免费视频| 亚洲精品永久免费精品| 亚洲欧洲日本在线| 亚洲精品系列| 99视频+国产日韩欧美| 一区二区三区高清不卡| 久久综合五月| 欧美va天堂| 欧美国产一区二区| 亚洲福利免费| 亚洲精品在线看| 一本色道久久88综合亚洲精品ⅰ| 一本到12不卡视频在线dvd| 日韩一级精品| 亚洲一区二区三区免费视频| 亚洲免费网站| 久久久久国产一区二区三区| 噜噜噜躁狠狠躁狠狠精品视频| 久久精品欧美日韩| 麻豆91精品| 欧美日韩爆操| 国产精品综合| 伊人蜜桃色噜噜激情综合| 亚洲人午夜精品| 在线亚洲美日韩| 性欧美暴力猛交另类hd| 久久米奇亚洲| 亚洲第一精品影视| aa国产精品| 久久国产加勒比精品无码| 欧美成人精品一区二区| 国产精品久久久久国产a级| 国产真实久久| 亚洲精品中文字| 性欧美videos另类喷潮| 欧美国产丝袜视频| 在线一区欧美| 免费观看久久久4p| 国产精品网站一区| 亚洲高清av| 亚洲欧美综合一区| 亚洲第一视频| 午夜精品美女久久久久av福利| 免费看的黄色欧美网站| 国产精品女主播一区二区三区| 在线观看欧美日韩国产| 亚洲女优在线| 亚洲第一黄色| 久久国产直播| 国产精品久久综合| 亚洲人成人一区二区在线观看| 性色av一区二区三区在线观看| 欧美高清在线一区| 欧美有码在线视频| 欧美视频中文字幕| 亚洲精品乱码久久久久久日本蜜臀| 欧美一区二粉嫩精品国产一线天| 亚洲国产精品久久久久秋霞不卡 | 欧美三级电影一区| 亚洲韩日在线| 久久久久中文| 亚洲欧美日韩网| 国产精品av久久久久久麻豆网| 亚洲人成网站精品片在线观看| 久久久久久网址| 先锋影音久久久| 国产麻豆91精品|