AC自動機-マルチモードストリングのマッチング運用---HDU 2896
4872 ワード
ウイルスによる侵略
Problem's Link:http://acm.hdu.edu.cn/showproblem.php?pid=2896
Mean:
中国語の問題は解釈しません.
アナリゼ:
AC自动机の运用により、マルチモードシリアルがマッチします.いくつかの細かい点に注意しなければならないです.これらの細部に長い間カードをかけました.
1)出力されたウェブサイト番号と最終的なウイルスサイト数は同じではない.
2)nextポインタは128を設定し、そうでないとスタックが破裂します.
3)同じ理屈で、charがintに変換する場合、baseは31に設定する.
Time complexity:o(n)+o(ml)
ソースコード:
Problem's Link:http://acm.hdu.edu.cn/showproblem.php?pid=2896
Mean:
中国語の問題は解釈しません.
アナリゼ:
AC自动机の运用により、マルチモードシリアルがマッチします.いくつかの細かい点に注意しなければならないです.これらの細部に長い間カードをかけました.
1)出力されたウェブサイト番号と最終的なウイルスサイト数は同じではない.
2)nextポインタは128を設定し、そうでないとスタックが破裂します.
3)同じ理屈で、charがintに変換する場合、baseは31に設定する.
Time complexity:o(n)+o(ml)
ソースコード:
// Memory Time
// 1347K 0MS
// by : Snarl_jsb
// 2014-09-30-11.01
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<climits>
#include<cmath>
#define LL long long
using namespace std;
const int N = 10010;
char str[N];
struct node
{
node *next[128]; // 128
node *fail; //
int count; //
int num;
node() //
{
for(int i = 0; i < 128; i++)
next[i] = NULL;
count = 0;
fail = NULL;
num=0;
}
}*q[50*N];
node *root;
int head, tail;
void Insert(char *str,int num) // . Trie
{
node *p = root;
int i = 0, index;
while(str[i]) {
index = str[i] - 31; //
if(p->next[index] == NULL) //
p->next[index] = new node(); //
p = p->next[index]; //
i++;
}
p->count++; //
p->num=num;
}
void build_ac_automation(node *root) // bfs fail
{
root->fail = NULL;
q[tail++] = root;
while(head < tail) {
node *temp = q[head++];
node *p = NULL;
for(int i = 0; i < 128; i++) {
if(temp->next[i] != NULL) {
if(temp == root) temp->next[i]->fail = root;
else {
p = temp->fail;
while(p != NULL) {
if(p->next[i] != NULL) {
temp->next[i]->fail = p->next[i];
break;
}
p = p->fail;
}
if(p == NULL) temp->next[i]->fail = root;
}
q[tail++] = temp->next[i];
}
}
}
}
int total=0;
int Query(node *root,int num) // +
{
int i = 0, cnt = 0, index;
node *p = root;
int idx=0;
int ans[100];
while(str[i])
{
index = str[i] - 31;
while(p->next[index] == NULL && p != root) // , count 0 ,
p = p->fail;// ,p p->fail.( KMP next )
p = p->next[index];// ,
if(p == NULL)
p = root; // , root,
node *temp = p;//
while(temp != root && temp->count != -1) // -- , count>1, ;
{
if(temp->count>0)
{
cnt ++; //
ans[++idx]=temp->num;
}
// temp->count = -1; // -1, cnt ,
temp = temp->fail;//
}
i++;
}
if(idx==0)
return 0;
printf("web %d: ",num);
sort(ans+1,ans+1+idx);
total++;
for(int i=1;i<idx;++i)
{
printf("%d ",ans[i]);
}
printf("%d
",ans[idx]);
return cnt;
}
int main()
{
int n;
cin>>n;
head=tail=0;
root=new node();
for(int i=1;i<=n;++i)
{
scanf("%s",str);
Insert(str, i);
}
build_ac_automation(root); //
int m;
cin>>m;
total=0;
for(int i=1;i<=m;++i)
{
scanf("%s",str);
Query(root,i);
}
printf("total: %d
",total);
return 0;
}