首页 > 代码库 > HDU P2222 Keywords Search
HDU P2222 Keywords Search
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.
--by HDU;
http://acm.hdu.edu.cn/showproblem.php?pid=2222
《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《
给一份Key_word和一串字符，查询有多少Ｋ＿ｗ在字串中；
唉，你看这题，你看她，她又是一道萝莉裸题，你不知道，裸题不能抄题解吗？
要自己打知道吗？
。。。。
本题显然是AC自动机，然而我却写成了TLE自动机（话说哪有数组开小就死循环的。。）
先建一棵trie
代码：
for(i=1;i<=n;i++){ getchar(); scanf("%s",key[i]); k=0; len=strlen(key[i])-1; for(j=0;j<=len;j++){ if(!data[k].ch[key[i][j]-‘a‘]) data[k].ch[key[i][j]-‘a‘]=++tot; k=data[k].ch[key[i][j]-‘a‘]; } is_end[k]++; }
（有关trie的,POJ P2001）
然后连上fail;
bfs顺序求fail保证先求父节点i再求子节点j，fail[j]=fail[i].ch(子节点的fail为父节点的fail的子节点或父节点的fai的faill的子节点或...);
代码：
void bfs_fail(){ memset(vis,0,sizeof(vis)); int i,j; que[1]=0;h=0;t=1; while(h<t){ ++h; for(i=0;i<=25;i++) if(data[que[h]].ch[i]){ j=que[h]; while(1){ if(data[j].ch[i]&&data[j].ch[i]!=data[que[h]].ch[i]){ fail[data[que[h]].ch[i]]=data[j].ch[i]; break;} else{ if(!j) break; j=fail[j]; } } t++; if(!vis[data[que[h]].ch[i]]){ que[t]=data[que[h]].ch[i]; vis[que[t]]=1; } } }}
这样自动机就建好了！！
然后是匹配:
代码：
//给我自动跑！！
请无视上行；
void match(){ int tem1=0,tem2=0,len; len=strlen(des); while(tem2!=len){ if(data[tem1].ch[des[tem2]-‘a‘]){ tem1=data[tem1].ch[des[tem2]-‘a‘]; tem2++; find(tem1); } else{ if(tem1==0) tem2++; tem1=fail[tem1]; } }}
你看到一个find（tem1）这是什么？
她的目的是在跑AC自动机时查询必须查询的值——查询未被查询的is_end标记，因为当我们查询到一个匹配的的点时，她的fail链上的is_end要被加入ans中，因为这些is_end所代表的key_word是你当匹配过的字符集（串？序列？）的后缀。
总代码如下：
1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 int n,ans; 5 char key[10001][101]; 6 struct ss{ 7 int ch[27]; 8 }data[500001]; 9 int tot; 10 int is_end[500001]; 11 int fail[500001]; 12 int que[500000],h,t; 13 char des[500001]; 14 int vis[500001]; 15 void bfs_fail(); 16 void work(); 17 void match(); 18 void find(int ); 19 int main() 20 { 21 int T; 22 scanf("%d",&T); 23 while(T--) 24 work(); 25 return 0; 26 } 27 void work() 28 { 29 int i,j,k,len; 30 memset(data,0,sizeof(data)); 31 memset(is_end,0,sizeof(is_end)); 32 memset(fail,0,sizeof(fail)); 33 scanf("%d",&n); 34 for(i=1;i<=n;i++){ 35 getchar(); 36 scanf("%s",key[i]); 37 k=0; 38 len=strlen(key[i])-1; 39 for(j=0;j<=len;j++){ 40 if(!data[k].ch[key[i][j]-‘a‘]) 41 data[k].ch[key[i][j]-‘a‘]=++tot; 42 k=data[k].ch[key[i][j]-‘a‘]; 43 } 44 is_end[k]++; 45 } 46 bfs_fail(); 47 getchar(); 48 scanf("%s",des); 49 ans=0;match(); 50 printf("%d\n",ans); 51 } 52 void bfs_fail() 53 { 54 memset(vis,0,sizeof(vis)); 55 int i,j; 56 que[1]=0;h=0;t=1; 57 while(h<t){ 58 ++h; 59 for(i=0;i<=25;i++) 60 if(data[que[h]].ch[i]){ 61 j=que[h]; 62 while(1){ 63 if(data[j].ch[i]&&data[j].ch[i]!=data[que[h]].ch[i]){ 64 fail[data[que[h]].ch[i]]=data[j].ch[i]; break;} 65 else{ 66 if(!j) 67 break; 68 j=fail[j]; 69 } 70 } 71 t++; 72 if(!vis[data[que[h]].ch[i]]){ 73 que[t]=data[que[h]].ch[i]; 74 vis[que[t]]=1; 75 } 76 } 77 } 78 } 79 void match() 80 { 81 int tem1=0,tem2=0,len; 82 len=strlen(des); 83 while(tem2!=len){ 84 if(data[tem1].ch[des[tem2]-‘a‘]){ 85 tem1=data[tem1].ch[des[tem2]-‘a‘]; 86 tem2++; 87 find(tem1); 88 } 89 else{ 90 if(tem1==0) 91 tem2++; 92 tem1=fail[tem1]; 93 } 94 } 95 } 96 void find(int tem) 97 { 98 int i; 99 while(tem){100 if(is_end[tem]){101 ans+=is_end[tem];102 is_end[tem]=0;103 }104 tem=fail[tem];105 }106 }
祝AC哟
HDU P2222 Keywords Search