AC自动机学习小记 Hdu 2222 Keywords Search (模板)

以你之姓@ 2023-06-04 06:59 8阅读 0赞

学习链接：http://wenku.baidu.com/view/4cf3374769eae009591bec05.html

题目集锦及解题报告：

[AC自动机专题-将狼踩尽 19891101][AC_-_ 19891101]

[AC自动机专题-yefeng1627][AC_-yefeng1627]

[AC自动机专题-E\_star][AC_-E_star]

以下代码参考了以上博文。

题意:求给定n个模式串在主串中出现了几个。(每一个模式串只被记录一次)

三种实现，指针版本最快。

#include <cstdio>
    #include <cstring>
    
    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;    //各种用途:计数,标号等
    		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 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++;
    		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];
    			}
    		}
    	}
    	
    	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[1000005],s[55];
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int T,i,n;
    	scanf("%d",&T);
    	while (T--)
    	{
    		scanf("%d",&n);
    		ac.Init();
    		for (i=1;i<=n;i++)
    			scanf("%s",s),ac.Insert(s);
    		scanf("%s",str);
    		ac.Build();
    		printf("%d\n",ac.Query(str));
    	}
    	return 0;
    }

#include <cstdio>
    #include <set>
    #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';
     
    class ACAutomaton
    {
    private:
    	int chd[MAXPT][size];
    	int val[MAXPT];//记录题目给的关键数据
    	int fail[MAXPT];//fail指针
    	int Q[MAXPT];//队列,用于广度优先计算fail指针
    	int ID[128];//字母对应的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 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]++;
    	}
    
    	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];
    			}
    		}
    	}
    
    	int 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 && val[rt] != -1)
    			{
    				ans += val[rt];
    				val[rt] = -1;
    				rt = fail[rt];
    			}
    		}
    		return ans;
    	}
    }ac;
    
    char str[1000005],s[55];
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int T,i,n;
    	scanf("%d",&T);
    	while (T--)
    	{
    		scanf("%d",&n);
    		ac.Init();
    		for (i=1;i<=n;i++)
    			scanf("%s",s),ac.Insert(s);
    		scanf("%s",str);
    		ac.Build();
    		printf("%d\n",ac.Query(str));
    	}
    	return 0;
    }

#include <iostream>
    #include <queue>
    #include <string.h>
    using namespace std;
    
    const int size=26;
    const int N=250005;
    
    struct Node
    {
    	int next[size],pre,leafn,flag;
    
    	void Init ()
    	{
    		memset(next,0,sizeof(next));
    		pre=-1,leafn=0,flag=0;
    	}
    }a[N];
    
    int e,n,root;
    char str[1000005],s[55];
    
    void Insert (char str[],int id)
    {
    	int p=root;
    	for (int i=0;str[i];i++)
    	{
    		if (a[p].next[str[i]-'a']==0)
    			a[p].next[str[i]-'a']=++e;
    		p=a[p].next[str[i]-'a'];
    	}
    	a[p].leafn++;
    }
    
    
    void Build_DFA ()
    {
    	int i,p,q,k;
    	queue<int> Q;
    	for (i=0;i<size;i++) a[0].next[i]=1;
    	a[0].pre=0,a[1].pre=0;
    	Q.push(1);
    	while (!Q.empty())
    	{
    		p=Q.front();
    		Q.pop();
    		for (i=0;i<size;i++) if (a[p].next[i])
    		{
    			q=a[p].next[i];
    			k=a[p].pre;
    			while (k!=-1)
    				if (a[k].next[i]) 
    				{
    					a[q].pre=a[k].next[i];
    					break;
    				}
    				else k=a[k].pre;
    			Q.push(q);
    		}
    	}
    }
    
    int Query (char str[])
    {
    	int ans=0;
    	int p=root,pre,k;
    	for (int i=0;str[i];i++)
    	{
    		k=str[i]-'a';
    		while (p>=1)
    			if (a[p].next[k])
    			{
    				p=a[p].next[k];
    				pre=p;
    				while (pre>=1 && a[pre].flag==0)
    				{
    					a[pre].flag=1;
    					ans+=a[pre].leafn;
    					pre=a[pre].pre;
    				}
    				break;
    			}
    			else p=a[p].pre;
    		if (p<1) p=1;
    	}
    	return ans;
    }
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int T,i;
    	scanf("%d",&T);
    	while (T--)
    	{
    		scanf("%d",&n);
    		root=e=1;
    		for (i=0;i<N;i++)
    			a[i].Init();
    		for (i=1;i<=n;i++)
    			scanf("%s",s),Insert(s,i);
    		scanf("%s",str);
    		Build_DFA();
    		printf("%d\n",Query(str));
    	}
    	return 0;
    }

[AC_-_ 19891101]: http://www.cnblogs.com/jianglangcaijin/category/431560.html
[AC_-yefeng1627]: http://www.cnblogs.com/yefeng1627/archive/2013/05/23/3094566.html
[AC_-E_star]: http://www.cnblogs.com/E-star/archive/2013/03/08/2950198.html