AC自动机总结 part1

客官°小女子只卖身不卖艺 2023-05-30 06:24 4阅读 0赞

这回总结的基本都是模板题……

**Hdu 2896 病毒侵袭**

用set统计哪些子串出现过。注意字符集并不只有a-z

#pragma warning(disable:4786)
    #include <set>
    #include <map>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <string>
    #include <vector>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    const int MAXPT=500007;   //最大节点数
    const int size=100;     //子节点数
    const char start=32;  //子节点标号对应关系
    
    
    set<int>iSet[1007];
     
    class Ac_Automat
    {
    private:
    	struct Node
    	{
    		Node *fail;
    		Node *next[size];
    		int cnt;    //各种用途
    		bool flag;   //是否为单词结束
    		void newnode () //生成节点
    		{
    			fail=NULL;
    			for (int i=0;i<size;i++)
    				next[i]=NULL;
    			cnt=0;
    			flag=false;
    		}
    	};
    	
    	Node *q[MAXPT],H[MAXPT],*root;
    	int fr,tl,t;
    public:
        void Init ()
    	{
    		fr = tl = 0;
    		t = 0;
    		H[t].newnode();
    		root = &H[t++];
    	}
    
    	void Insert (char *s,int id)
    	{
    		int len = strlen(s);
    		Node *p = root;
    		for (int i=0;i<len;i++)
    		{
    			int k = s[i] - start;
                if (p->next[k] == NULL)
                {
    				H[t].newnode();
    				p->next[k] = &H[t++];
    			}
    			p = p->next[k];
    		}
    		p->cnt=id;
    		p->flag=true;
    	}
    
        void Build ()
    	{
    		root->fail = NULL;
    		q[tl] = root;
    		while (fr <= tl)
    		{
    			Node *tmp = q[fr++];
    			Node *p = NULL;
    			for (int i=0;i<size;i++) if (tmp->next[i])
    			{
    				if (tmp == root)
    					tmp->next[i]->fail = root;
    				else
    				{
    					p = tmp->fail;
    					while (p != NULL)
    					{
    						if (p->next[i])
    						{
    							tmp->next[i]->fail = p->next[i];
    							break;
    						}
    						p = p->fail;
    					}
    					if (p == NULL) 
    						tmp->next[i]->fail = root;
    				}
    				q[++tl] = tmp->next[i];
    			}
    		}
    	}
    	
    	void Query (char *s,int id)
    	{
    		Node *p = root;
    		int len = strlen(s);
    		for (int i=0;i<len;i++)
    		{
    			int k = s[i] - start;
    			while (p->next[k] == NULL && p != root)
    				p = p->fail;
    			
    			p = p->next[k];
    			if (p == NULL) p = root;
    			Node *tmp = p;
    			while (tmp != root)
    			{
    				if (tmp->cnt != 0)
    					iSet[id].insert(tmp->cnt);
    				tmp = tmp->fail;
    			}
    		}
    	}
    }ac;
    
    char s1[202],s2[10007];
     
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int i,m,n;
    	while (~scanf("%d",&n))
    	{
    		ac.Init();
    		for (i=0;i<=1000;i++)
    			iSet[i].clear();
    
    		for (i=1;i<=n;i++)
    		{
    			scanf("%s",s1);
    			ac.Insert(s1,i);
    		}
    		ac.Build();
    		scanf("%d",&m);
    		for (i=1;i<=m;i++)
    		{
    			scanf("%s",s2);
    			ac.Query(s2,i);
    		}
    		int tol = 0;
    		set<int>::iterator it;
    		for (i=1;i<=m;i++) if (iSet[i].size() >= 1)
    		{
    			printf("web %d:",i);
    			tol++;
    			for (it=iSet[i].begin(); it!=iSet[i].end();it++)
    				printf(" %d",*it);
    			printf("\n");
    		}
    		printf("total: %d\n",tol);
    	}
    	return 0;
    }

**Hdu 3065 病毒侵袭持续中**

此题模板串无重复

思路：AC自动机统计模板串出现次数

#include <cstdio>
    #include <set>
    #include <cctype>
    #include <algorithm>
    #include <map>
    #include <cstring>
    #include <queue>
    using namespace std;
    
    
    const int MAXPT = 500007;  //MAXPT = StringNumber * StringLength
    const int size = 26;
    const char start='a';
    
    int num[155];
     
    class ACAutomaton
    {
    private:
    	int chd[MAXPT][size];
    	int val[MAXPT];//记录题目给的关键数据
    	int fail[MAXPT];//fail指针
    	int Q[MAXPT];//队列,用于广度优先计算fail指针
    	int ID[228];//字母对应的I
    	int sz;//已使用节点个数
    
    public:
        
    	void Set ()//初始化,计算字母对应的儿子ID,如:'a'->0 ... 'z'->25
    	{
    		fail[0]=0;
    		for (int i=0;i<size;i++)
    			ID[i+start] = i;
    	}
        
    	void Init ()
    	{
    		Set();
    		memset(chd[0],0,sizeof(chd[0]));
    		sz = 1;
    	}
        
    	void Insert (char *a,int id)
    	{
    		int p=0;
    		for (; *a ; a++)
    		{
    			int c = ID[*a];
    			if (!chd[p][c])
    			{
    				memset(chd[sz] , 0 , sizeof(chd[sz]));
    				val[sz]=0;
    				chd[p][c] = sz++;
    			}
    			p = chd[p][c];
    		}
    		val[p]=id;
    	}
    
    	void Build ()
    	{
    		int *s=Q, *e=Q,i;
    		for (i=0;i<size;i++)
    			if (chd[0][i])
    			{
    				fail[ chd[0][i] ] = 0;
    				*e ++ = chd[0][i];
                }
    
    		while (s != e)
    		{
    			int u = *s++;
    			for (i=0;i<size;i++)
    			{
    				int &v = chd[u][i];
    				if (v)
    				{
    					*e ++ = v;
    					fail[v] = chd[ fail[u] ][i];
    				}
    				else
    					v = chd[ fail[u] ][i];
    			}
    		}
    	}
    
    	void Query (char *s)
    	{
    		int p=0,k,ans=0;
    		for (; *s; s++)
    		{
    			k = ID[*s];
    			while (!chd[p][k] && p!=0)
    				p = fail[p];
    			
    			p = chd[p][k];
    			int rt = p;
    			while (rt != 0)
    			{
    				if (val[rt] != 0)
    					num[val[rt]]++;
    				rt = fail[rt];
    			}
    		}
    	}
    }ac;
    
    char str[1000005],s[155][75];
    int ans[155];
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int i,n;
    	while (scanf("%d",&n),n)
    	{
    		ac.Init();
    		memset(num,0,sizeof(num));
    		memset(ans,0,sizeof(ans));
    		for (i=1;i<=n;i++)
    			scanf("%s",s[i]),ac.Insert(s[i],i);
    		
    		scanf("%s",str);
    		ac.Build();
    		ac.Query(str);
    		int cnt=0,len=-1;
    		for (i=1;i<=n;i++)
    		{
    			if (num[i]>len)
    			{
    				cnt=0;
    				ans[++cnt]=i;
    				len=num[i];
    			}
    			else if (num[i]==len)
    				ans[++cnt]=i;
    		}
    		printf("%d\n",len);
    		for (i=1;i<=cnt;i++)
    			printf("%s\n",s[ans[i]]);
    	}
    	return 0;
    }

**Hdu 3695 Computer Virus on Planet Pandora**

题意：给出一些病毒串以及一个大串s，若s包含一个病毒串或其反串，则我们说其包含该病毒串。问s包含了多少病毒串？

题意：将病毒串插入自动机。用s以及其反串跑一遍。

#include <cstdio>
    #include <cctype>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    const int MAXPT=500007;   //最大节点数
    const int size=26;     //子节点数
    const char start='A';  //子节点标号对应关系
     
    class Ac_Automat
    {
    private:
    	struct Node
    	{
    		Node *fail;
    		Node *next[size];
    		int cnt;    //各种用途:计数,标号等
    		void newnode () //生成节点
    		{
    			fail=NULL;
    			for (int i=0;i<size;i++)
    				next[i]=NULL;
    			cnt=0;
    		}
    	};
    	
    	Node *q[MAXPT],H[MAXPT],*root;
    	int fr,tl,t;
    public:
    	void Init ()
    	{
    		fr = tl = 0;
    		t = 0;
    		H[t].newnode();
    		root = &H[t++];
    	}
    
    	void Insert (char *s)
    	{
    		int len = strlen(s);
    		Node *p = root;
    		for (int i=0;i<len;i++)
    		{
    			int k = s[i] - start;
    			if (p->next[k] == NULL)
    			{
    				H[t].newnode();
    				p->next[k] = &H[t++];
    			}
    			p = p->next[k];
    		}
    		p->cnt++;
    	}
    
    	void Build ()
    	{
    		root->fail = NULL;
    		q[tl] = root;
    		while (fr <= tl)
    		{
    			Node *tmp = q[fr++];
    			Node *p = NULL;
    			for (int i=0;i<size;i++) if (tmp->next[i])
    			{
    				if (tmp == root)
    					tmp->next[i]->fail = root;
    				else
    				{
    					p = tmp->fail;
    					while (p != NULL)
    					{
    						if (p->next[i])
    						{
    							tmp->next[i]->fail = p->next[i];
    							break;
    						}
    						p = p->fail;
    					}
    					if (p == NULL) 
    						tmp->next[i]->fail = root;
    				}
    				q[++tl] = tmp->next[i];
    			}
    		}
    	}
    	
    	int Query (char *s)
    	{
    		int res = 0;
    		Node *p = root;
    		int len = strlen(s);
    		for (int i=0;i<len;i++)
    		{
    			int k = s[i] - start;
    			while (p->next[k] == NULL && p != root)
    				p = p->fail;
    			
    			p = p->next[k];
    			if (p == NULL) p = root;
    			Node *tmp = p;
    			while (tmp != root && tmp->cnt != -1)
    			{
    				res += tmp->cnt;
    				tmp->cnt = - 1;
    				tmp = tmp->fail;
    			}
    		}
    		return res;
    	}
    }ac;
    
    char str[5100000+10],s[5100000+10];
    
    void reverse (char *s)
    {
    	int len=strlen(s);
    	int L=0,R=len-1;
    	while (L<R)
    		swap(s[L++],s[R--]);
    }
    
    void Deal ()
    {
    	int len=strlen(s),L=0;
    	for (int i=0;i<len;i++)
    	{
    		if (isupper(s[i]))
    			str[L++]=s[i];
    		else if (s[i]=='[')
    		{
    			int k=0,j=i+1;
    			while (isdigit(s[j]))
    			{
    				k=k*10+s[j]-'0';
    				j++;
    			}
    			i=j+1;
    			for (int t=0;t<k;t++)
    				str[L++]=s[j];
    		}
    		str[L]=0;
    	}
    	int ans=ac.Query(str);
    	reverse(str);
    	ans+=ac.Query(str);
    	printf("%d\n",ans);
    }
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int T,n;
    	scanf("%d",&T);
    	while (T--)
    	{
    		scanf("%d",&n);
    		ac.Init();
    		for (int i=1;i<=n;i++)
    			scanf("%s",s),ac.Insert(s);
    		ac.Build();
    		scanf("%s",s);
    		Deal ();
    	}
    	return 0;
    }

**BZoj 3172: \[Tjoi2013\]单词**

题目连接：http://61.187.179.132/JudgeOnline/problem.php?id=3172

ascll码表比a小1的字符是 \` ，用这个字符作为分割，将所有模式串连起来作为主串，用模式串构造自动机。然后就跟前面几道统计出现次数的题没有区别了。

注意会有重复的单词，我用了map映射来处理。

这个题貌似后缀数组也可以搞。

#pragma warning(disable:4786)
    #include <cstdio>
    #include <set>
    #include <cctype>
    #include <algorithm>
    #include <string>
    #include <map>
    #include <cstring>
    #include <queue>
    
    using namespace std;
    
    const int MAXPT = 4000007;  //MAXPT = StringNumber * StringLength
    const int size = 27;
    const char start='`';
    
    int num[205];
     
    class ACAutomaton
    {
    private:
    	int chd[MAXPT][size];
    	int val[MAXPT];//记录题目给的关键数据
    	int fail[MAXPT];//fail指针
    	int Q[MAXPT];//队列,用于广度优先计算fail指针
    	int ID[228];//字母对应的I
    	int sz;//已使用节点个数
    
    public:
        
    	void Set ()//初始化,计算字母对应的儿子ID,如:'a'->0 ... 'z'->25
    	{
    		fail[0]=0;
    		for (int i=0;i<size;i++)
    			ID[i+start] = i;
    	}
        
    	void Init ()
    	{
    		Set();
    		memset(chd[0],0,sizeof(chd[0]));
    		sz = 1;
    	}
        
    	void Insert (char *a,int id)
    	{
    		int p=0;
    		for (; *a ; a++)
    		{
    			int c = ID[*a];
    			if (!chd[p][c])
    			{
    				memset(chd[sz] , 0 , sizeof(chd[sz]));
    				val[sz]=0;
    				chd[p][c] = sz++;
    			}
    			p = chd[p][c];
    		}
    		val[p]=id;
    	}
    
    	void Build ()
    	{
    		int *s=Q, *e=Q,i;
    		for (i=0;i<size;i++)
    			if (chd[0][i])
    			{
    				fail[ chd[0][i] ] = 0;
    				*e ++ = chd[0][i];
                }
    
    		while (s != e)
    		{
    			int u = *s++;
    			for (i=0;i<size;i++)
    			{
    				int &v = chd[u][i];
    				if (v)
    				{
    					*e ++ = v;
    					fail[v] = chd[ fail[u] ][i];
    				}
    				else
    					v = chd[ fail[u] ][i];
    			}
    		}
    	}
    
    	void Query (char *s)
    	{
    		int p=0,k,ans=0;
    		for (; *s; s++)
    		{
    			k = ID[*s];
    			while (!chd[p][k] && p!=0)
    				p = fail[p];
    			
    			p = chd[p][k];
    			int rt = p;
    			while (rt != 0)
    			{
    				if (val[rt] != 0)
    					num[val[rt]]++;
    				rt = fail[rt];
    			}
    		}
    	}
    }ac;
    
    char str[100005*205],s[205][100005];
    
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int n,i;
    	while (~scanf("%d",&n))
    	{
    		map<string,int> mp;
    		ac.Init();
    		memset(num,0,sizeof(num));
    		memset(str,0,sizeof(str));    /// 
    		for (i=1;i<=n;i++)
    		{
    			scanf("%s",s[i]);
    			if (mp[s[i]]==0)
    			{
    				mp[s[i]]=i;
    				ac.Insert(s[i],i);	
    			}
    			strcat(str,s[i]);
    			strcat(str,"`");
    		}
    		ac.Build();
    		ac.Query(str);
    		for (i=1;i<=n;i++)
    			printf("%d\n",num[mp[s[i]]]);
    	}
    	return 0;
    }

**LightOJ 1427 Substring Frequency (II)**

题目链接：http://lightoj.com/volume\_showproblem.php?problem=1427

还是统计出现次数，有重复的单词。

#pragma warning(disable:4786)
    #include <cstdio>
    #include <set>
    #include <cctype>
    #include <algorithm>
    #include <string>
    #include <map>
    #include <cstring>
    #include <queue>
    
    using namespace std;
    
    
    const int MAXPT = 1000007;  //MAXPT = StringNumber * StringLength
    const int size = 26;
    const char start='a';
    
    int num[505];
     
    class ACAutomaton
    {
    private:
    	int chd[MAXPT][size];
    	int val[MAXPT];//记录题目给的关键数据
    	int fail[MAXPT];//fail指针
    	int Q[MAXPT];//队列,用于广度优先计算fail指针
    	int ID[228];//字母对应的I
    	int sz;//已使用节点个数
    
    public:
        
    	void Set ()//初始化,计算字母对应的儿子ID,如:'a'->0 ... 'z'->25
    	{
    		fail[0]=0;
    		for (int i=0;i<size;i++)
    			ID[i+start] = i;
    	}
        
    	void Init ()
    	{
    		Set();
    		memset(chd[0],0,sizeof(chd[0]));
    		sz = 1;
    	}
        
    	void Insert (char *a,int id)
    	{
    		int p=0;
    		for (; *a ; a++)
    		{
    			int c = ID[*a];
    			if (!chd[p][c])
    			{
    				memset(chd[sz] , 0 , sizeof(chd[sz]));
    				val[sz]=0;
    				chd[p][c] = sz++;
    			}
    			p = chd[p][c];
    		}
    		val[p]=id;
    	}
    
    	void Build ()
    	{
    		int *s=Q, *e=Q,i;
    		for (i=0;i<size;i++)
    			if (chd[0][i])
    			{
    				fail[ chd[0][i] ] = 0;
    				*e ++ = chd[0][i];
                }
    
    		while (s != e)
    		{
    			int u = *s++;
    			for (i=0;i<size;i++)
    			{
    				int &v = chd[u][i];
    				if (v)
    				{
    					*e ++ = v;
    					fail[v] = chd[ fail[u] ][i];
    				}
    				else
    					v = chd[ fail[u] ][i];
    			}
    		}
    	}
    
    	void Query (char *s)
    	{
    		int p=0,k,ans=0;
    		for (; *s; s++)
    		{
    			k = ID[*s];
    			while (!chd[p][k] && p!=0)
    				p = fail[p];
    			
    			p = chd[p][k];
    			int rt = p;
    			while (rt != 0)
    			{
    				if (val[rt] != 0)
    					num[val[rt]]++;
    				rt = fail[rt];
    			}
    		}
    	}
    }ac;
    
    char str[1000005],s[505][505];
    
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int T,n,i;
    	scanf("%d",&T);
    	for (int Cas=1;Cas<=T;Cas++)
    	{
    		map <string,int> mp;
    		printf("Case %d:\n",Cas);
    		scanf("%d",&n);
    		scanf("%s",str);
    		ac.Init();
    		memset(num,0,sizeof(num));
    		for (i=1;i<=n;i++)
    		{
    			scanf("%s",s[i]);
    			if (mp[s[i]]==0)
    			{
    				mp[s[i]]=i;
    				ac.Insert(s[i],i);
    			}
    		}
    		ac.Build();
    		ac.Query(str);
    		for (i=1;i<=n;i++)
    			printf("%d\n",num[mp[s[i]]]);
    	}
    	return 0;
    }