AC自动机：
-
求多个字符串是否在主串中出现过。可依据情况分别求出出现次数，出现位置等。
AC自动机入门
Keywords Search
指针多叉树
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
const int MAXN=4000010;
const int BASE=26;
struct Node
{
Node *fail;
Node *next[26];
int cnt;
void init()
{
fail=NULL;
memset(next,NULL,sizeof(next));
cnt=0;
}
};
Node *root;
void put(char *str)
{
Node *p=root;
int len=strlen(str);
for(int i=0;i<len;i++)
{
int pos=str[i]-'a';
if(p->next[pos]==NULL)
{
p->next[pos]=new Node();
p->next[pos]->init();
p=p->next[pos];
}
else p=p->next[pos];
}
p->cnt++;//题目含有重复模式串
}
void getFail()
{
queue<Node *>que;
Node *temp,*son,*p=root;
que.push(p);
while(!que.empty())
{
Node *curr=que.front();
que.pop();
for(int i=0;i<26;i++)
{
son=curr->next[i];
if(son!=NULL)
{
if(curr==root)
{
son->fail=root;
}
else
{
p=curr->fail;
while(p!=NULL)
{
if(p->next[i]!=NULL)
{
son->fail=p->next[i];
break;
}
p=p->fail;
}
if(p==NULL) son->fail=root;
}
que.push(son);
}
}
}
}
void query(char *str)
{
int len=strlen(str);
Node *p=root,*temp;
int sum=0;
for(int i=0;i<len;i++)
{
int pos=str[i]-'a';
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->cnt>=0)//这里直接把没访问过的节点设置为访问状态,加速搜索(因为题目求的是出现过的模式串,只求一次)
{
sum+=temp->cnt;
temp->cnt=-1;
}
else break;//节点已经访问过了,直接break
temp=temp->fail;
}
}
printf("%d\n",sum);
}
int main()
{
char str[1000000+100];
int cas,n;
scanf("%d",&cas);
while(cas--)
{
root=new Node();
root->init();
scanf("%d",&n);
int i;
getchar();
for(i=0;i<n;i++)
{
gets(str);
put(str);
}
getFail();
gets(str);
query(str);
}
return 0;
}
数组多叉树
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
const int MAXN=4000010;
const int BASE=26;
struct Node
{
int cnt;
int fail;
int next[26];
};
Node trie[MAXN];
int trie_s;
void insert(char *str)
{
int len=strlen(str);
int p=1;
for(int i=0;i<len;i++)
{
int pos=str[i]-'a';
if(!trie[p].next[pos])
{
trie[p].next[pos]=++trie_s;
memset(trie[trie[p].next[pos]].next,0,sizeof(trie[trie[p].next[pos]].next));
trie[trie[p].next[pos]].cnt=0;
trie[trie[p].next[pos]].fail=0;
}
p=trie[p].next[pos];
}
trie[p].cnt++;
}
void getFail()
{
queue<int> que;
int son,p=1,temp;
que.push(p);
while(!que.empty())
{
int curr=que.front();
que.pop();
for(int i=0;i<26;i++)
{
son=trie[curr].next[i];
if(son)
{
if(curr==1) trie[son].fail=1;
else
{
temp=trie[curr].fail;
while(temp!=0)
{
if(trie[temp].next[i])
{
trie[son].fail=trie[temp].next[i];
break;
}
temp=trie[temp].fail;
}
if(temp==0) trie[son].fail=1;
}
que.push(son);
}
}
}
}
void query(char *str)
{
int cnt=0;
int len=strlen(str);
int p=1,temp;
for(int i=0;i<len;i++)
{
int pos=str[i]-'a';
while(!trie[p].next[pos]&&p!=1) p=trie[p].fail;
p=trie[p].next[pos];
if(!p) p=1;
temp=p;
while(temp!=1)
{
if(trie[temp].cnt>=0)//
{
cnt+=trie[temp].cnt;
trie[temp].cnt=-1;
}
else break;
temp=trie[temp].fail;
}
}
printf("%d\n",cnt);
}
int main()
{
char str[1000000+100];
int cas,n;
scanf("%d",&cas);
while(cas--)
{
trie_s=1;
trie[1].cnt=0;
trie[1].fail=0;
memset(trie[1].next,0,sizeof(trie[1].next));
scanf("%d",&n);
int i;
getchar();
for(i=0;i<n;i++)
{
gets(str);
insert(str);
}
getFail();
gets(str);
query(str);
}
return 0;
}
病毒侵袭持续中
指针多叉树
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=1010;
char virus[MAXN][55];
int num[MAXN];
struct Node
{
Node *fail;
Node *next[28];
int id;
void init()
{
id=-1;
fail=NULL;
memset(next,NULL,sizeof(next));
}
};
Node *root;
void insert(char *str,int id)
{
int len=strlen(str);
Node *p=root;
for(int i=0;i<len;i++)
{
int pos=str[i]-'A';
if(p->next[pos]==NULL)
{
p->next[pos]=new Node();
p->next[pos]->init();
}
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<28;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);
}
}
}
}
void query(char *str)
{
int len=strlen(str);
Node *p=root,*temp;
for(int i=0;i<len;i++)
{
int pos=str[i]-'A';
if(pos<0||pos>26) pos=27;
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!=-1)//这里只查询是病毒尾的节点;
{
num[temp->id]++;
}
temp=temp->fail;
}
}
}
int main()
{
char str[2000000+100];
int n;
while(scanf("%d",&n)!=EOF)
{
root=new Node();
root->init();
for(int i=1;i<=n;i++)
{
scanf("%s",virus[i]);
insert(virus[i],i);
num[i]=0;
}
getFail();
getchar();
gets(str);
query(str);
for(int i=1;i<=n;i++)
{
if(num[i]) printf("%s: %d\n",virus[i],num[i]);
}
}
return 0;
}
数组多叉树
填坑,待补充
填坑,待补充
填坑,待补充
网友评论