#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN=4000010;
int arr[5];
struct Node
{
int id;
int curr;
Node *fail;
Node *next[128];
void init()
{
id=0;
curr=0;
fail=NULL;
memset(next,NULL,sizeof(next));
}
};
Node *root;
void insert(char *str,int id)
{
Node *p=root;
int len=strlen(str);
for(int i=0;i<len;i++)
{
int pos=str[i];
if(p->next[pos]==NULL)
{
p->next[pos]=new Node();
p->next[pos]->init();
p=p->next[pos];
}
else p=p->next[pos];
}
p->id=id;
}
void getFail()
{
Node *temp,*son,*p=root;
queue<Node *> que;
que.push(p);
while(!que.empty())
{
Node *curr=que.front();
que.pop();
for(int i=0;i<128;i++)
{
son=curr->next[i];
if(son!=NULL)
{
if(curr==root) son->fail=root;
else
{
temp=curr->fail;
while(temp!=NULL)
{
if(temp->next[i]!=NULL)
{
son->fail=temp->next[i];
break;
}
temp=temp->fail;
}
if(temp==NULL) son->fail=root;
}
que.push(son);
}
}
}
}
bool query(char *str,int curr)
{
int len=strlen(str);
Node *temp,*p=root;
bool flag=false;
int index=0;
for(int i=0;i<len;i++)
{
int pos=str[i];
while(p->next[pos]==NULL&&p!=root) p=p->fail;
p=p->next[pos];
if(p==NULL) p=root;
temp=p;
while(temp!=root)
{
if(temp->id>0&&temp->curr!=curr)
{
flag=true;
temp->curr=curr;
arr[index++]=temp->id;
if(index>=3) break;
}
else break;
temp=temp->fail;
}
if(index>=3) break;
}
if(flag)
{
sort(arr,arr+index);
printf("web %d:",curr);
for(int j=0;j<index;j++)
printf(" %d",arr[j]);
printf("\n");
return true;
}
return false;
}
int main()
{
char virus[205];
char web[10010];
root=new Node();
root->init();
int n,m,total=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%s",virus);
insert(virus,i+1);
}
getFail();
scanf("%d",&m);
for(int i=0;i<m;i++)
{
scanf("%s",web);
if(query(web,i+1))
{
total++;
}
}
printf("total: %d\n",total);
return 0;
}
AC自動機_多組字符串匹配
最后編輯于 :
?著作權歸作者所有,轉載或內容合作請聯系作者
- 文/潘曉璐 我一進店門啃洋,熙熙樓的掌柜王于貴愁眉苦臉地迎上來传货,“玉大人,你說我怎么就攤上這事宏娄∥试#” “怎么了?”我有些...
- 文/不壞的土叔 我叫張陵孵坚,是天一觀的道長粮宛。 經常有香客問我,道長卖宠,這世上最難降的妖魔是什么巍杈? 我笑而不...
- 正文 為了忘掉前任,我火速辦了婚禮扛伍,結果婚禮上筷畦,老公的妹妹穿的比我還像新娘。我一直安慰自己刺洒,他們只是感情好鳖宾,可當我...
- 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著逆航,像睡著了一般鼎文。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上因俐,一...
- 文/蒼蘭香墨 我猛地睜開眼袍嬉,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了灶平?” 一聲冷哼從身側響起伺通,我...
- 正文 年R本政府宣布柏锄,位于F島的核電站酿箭,受9級特大地震影響,放射性物質發(fā)生泄漏趾娃。R本人自食惡果不足惜缭嫡,卻給世界環(huán)境...
- 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望抬闷。 院中可真熱鬧妇蛀,春花似錦、人聲如沸饶氏。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽疹启。三九已至古程,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間喊崖,已是汗流浹背挣磨。 一陣腳步聲響...