AC自动机

OI&ACM, 字符串
  1. 1 【hdu 2222】Keywords Search
  2. 2 【hdu 2896】病毒侵袭
  3. 3 【hdu 3065】病毒侵袭持续中
  4. 4 【poj 2778】DNA Sequence
  5. 5 【hdu 2243】考研路茫茫——单词情结

trie+kmp=AC自动机

1 【hdu 2222】Keywords Search

找模式串有多少在总串中出现过

这不是个模板题吗 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int N=50*10000+5;
int T,n,tot,tag[N],fail[N],trie[N][26];
char s[1000000];
void Add()
{
	int len=strlen(s),pre=0;
	for(int i=0;i<len;i++)
	{
		if(trie[pre][s[i]-'a']==-1)
		{
			trie[pre][s[i]-'a']=++tot;
			for(int j=0;j<26;j++) trie[tot][j]=-1;
			tag[tot]=0;
		} 
		pre=trie[pre][s[i]-'a'];
	}
	tag[pre]++;
}
void Construct()
{
	queue<int> Q;
	fail[0]=0;
	for(int i=0;i<26;i++)
	{
		if(trie[0][i]!=-1) fail[trie[0][i]]=0,Q.push(trie[0][i]);
		else trie[0][i]=0;
	}
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		for(int i=0;i<26;i++)
		{
			if(trie[x][i]!=-1)
			{
				Q.push(trie[x][i]);
				fail[trie[x][i]]=trie[fail[x]][i];
			}
			else trie[x][i]=trie[fail[x]][i];
		}
	}
}
int Solve()
{
	int pre=0,sum=0,len=strlen(s);
	for(int i=0;i<len;i++)
	{
		pre=trie[pre][s[i]-'a'];
		for(int j=pre;j;j=fail[j])
		  sum+=tag[j],tag[j]=0;
	}
	return sum;
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);tot=0;tag[0]=0;
		for(int i=0;i<26;i++) trie[0][i]=-1;
		while(n--)
		  scanf("%s",s),Add();
		Construct();
		scanf("%s",s);
		printf("%d\n",Solve());
	}
	return 0;
}

2 【hdu 2896】病毒侵袭

找哪些网站有哪些病毒

注意solve函数，不要算重了
还有要开128，因为是所有字符 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int N=500*200+5;
int n,tot,sum,ans[501],tag[N],fail[N],trie[N][128];
char s[10000];
bool used[501];
void Add(int t)
{
	int len=strlen(s),pre=0;
	for(int i=0;i<len;i++)
	{
		if(trie[pre][s[i]]==-1)
		{
			trie[pre][s[i]]=++tot;
			for(int j=0;j<128;j++) trie[tot][j]=-1;
			tag[tot]=0;
		} 
		pre=trie[pre][s[i]];
	}
	tag[pre]=t;
}
void AC()
{
	queue<int> Q;
	fail[0]=0;
	for(int i=0;i<128;i++)
	{
		if(trie[0][i]!=-1) fail[trie[0][i]]=0,Q.push(trie[0][i]);
		else trie[0][i]=0;
	}
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		for(int i=0;i<128;i++)
		{
			if(trie[x][i]!=-1)
			{
				Q.push(trie[x][i]);
				fail[trie[x][i]]=trie[fail[x]][i];
			}
			else trie[x][i]=trie[fail[x]][i];
		}
	}
}
void Solve(int t)
{
	int pre=0,len=strlen(s);
	ans[0]=0;memset(used,0,sizeof(used));
	for(int i=0;i<len;i++)
	{
		pre=trie[pre][s[i]];
		for(int j=pre;j;j=fail[j])
		  if(tag[j]&&!used[tag[j]])
		    ans[++ans[0]]=tag[j],used[tag[j]]=1;
	}
	if(ans[0])
	{
		sum++;
		sort(ans+1,ans+ans[0]+1);
		printf("web %d:",t);
		for(int i=1;i<=ans[0];i++) printf(" %d",ans[i]);
		printf("\n");
	}
}
int main()
{
	scanf("%d",&n);
	tag[0]=0;
	for(int i=0;i<128;i++) trie[0][i]=-1;
	for(int i=1;i<=n;i++)
	  scanf("%s",s),Add(i);
	AC();
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	  scanf("%s",s),Solve(i);
	printf("total: %d\n",sum);
	return 0;
}

3 【hdu 3065】病毒侵袭持续中

找病毒出现的次数

多组数据也不说一声。。。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int N=50005;
int T,n,tot,ans[1001],tag[N],fail[N],trie[N][128];
char s[2000000],a[1001][50];
void Add(int t)
{
	int len=strlen(a[t]),pre=0;
	for(int i=0;i<len;i++)
	{
		if(trie[pre][a[t][i]]==-1)
		{
			trie[pre][a[t][i]]=++tot;
			for(int j=0;j<128;j++) trie[tot][j]=-1;
			tag[tot]=0;
		} 
		pre=trie[pre][a[t][i]];
	}
	tag[pre]=t;
}
void AC()
{
	queue<int> Q;
	fail[0]=0;
	for(int i=0;i<128;i++)
	{
		if(trie[0][i]!=-1) fail[trie[0][i]]=0,Q.push(trie[0][i]);
		else trie[0][i]=0;
	}
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		for(int i=0;i<128;i++)
		{
			if(trie[x][i]!=-1)
			{
				Q.push(trie[x][i]);
				fail[trie[x][i]]=trie[fail[x]][i];
			}
			else trie[x][i]=trie[fail[x]][i];
		}
	}
}
void Solve()
{
	int pre=0,len=strlen(s);
	memset(ans,0,sizeof(ans));
	for(int i=0;i<len;i++)
	{
		pre=trie[pre][s[i]];
		for(int j=pre;j;j=fail[j])
		  if(tag[j]) ans[tag[j]]++;
	}
}
int main()
{
	while(scanf("%d",&n)==1)
	{
		tot=0;tag[0]=0;
		for(int i=0;i<128;i++) trie[0][i]=-1;
		for(int i=1;i<=n;i++)
		  scanf("%s",a[i]),Add(i);
		AC();
		scanf("%s",s);
		Solve();
		for(int i=1;i<=n;i++)
		  if(ans[i]) printf("%s: %d\n",a[i],ans[i]);
	}
	return 0;
}

4 【poj 2778】DNA Sequence

有ATCG的DNA，有m种排列为患病，求长度为n中正常的数量

看到题目的第一眼，我开始读：D(dǐ)NA序列。。。。。。陈林大法好。。。
算了不扯了。。。
AC自动机+矩阵乘法
先是RE了，因为我把tot写成了n
然后TLE了，解决方法是矩阵开long long，然后把mod写到外面 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int N=105;
const int mod=100000;
int m,n,tot,id[26],fail[N],trie[N][4];
long long ans,g[N][N],res[N][N],c[N][N];
char s[10];
bool tag[N];
void Add()
{
	int len=strlen(s),pre=0;
	for(int i=0,ID;i<len;i++)
	{
		ID=id[s[i]-'A'];
		if(trie[pre][ID]==-1)
		{
			trie[pre][ID]=++tot;
			for(int j=0;j<26;j++) trie[tot][j]=-1;
			tag[tot]=0;
		}
		pre=trie[pre][ID];
	}
	tag[pre]=1;
}
void Construct()
{
	queue<int> Q;
	fail[0]=0;
	for(int i=0;i<4;i++)
	{
		if(trie[0][i]!=-1) fail[trie[0][i]]=0,Q.push(trie[0][i]);
		else trie[0][i]=0;
	}
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		if(tag[fail[x]]) tag[x]=1; 
		for(int i=0;i<4;i++)
		{
			if(trie[x][i]!=-1)
			{
				Q.push(trie[x][i]);
				fail[trie[x][i]]=trie[fail[x]][i];
			}
			else trie[x][i]=trie[fail[x]][i];
		}
	}
	for(int i=0;i<=tot;i++)
	  for(int j=0;j<4;j++)
	    if(!tag[i]&&!tag[trie[i][j]]) g[i][trie[i][j]]++;
}
void Multi(long long a[N][N],long long b[N][N],int flag)
{
	memset(c,0,sizeof(c));
	for(int i=0;i<=tot;i++)
	  for(int j=0;j<=tot;j++)
	  {
	  	for(int k=0;k<=tot;k++)
	      c[i][j]+=a[i][k]*b[k][j];
	    c[i][j]%=mod;
	  }  
	if(!flag) memcpy(g,c,sizeof(g));
	else memcpy(res,c,sizeof(c));
}
void power(int b)
{
	for(int i=0;i<N;i++)  res[i][i]=1;
	for(;b;b>>=1,Multi(g,g,0))
	  if(b&1) Multi(res,g,1);
}
int main()
{
	scanf("%d%d",&m,&n);
	id['A'-'A']=0;id['T'-'A']=1;id['C'-'A']=2;id['G'-'A']=3;
	tot=0;tag[0]=0;
	for(int i=0;i<4;i++) trie[0][i]=-1;
	while(m--)
	  scanf("%s",s),Add();
	Construct();
	power(n);
	for(int i=0;i<=tot;i++)
	  ans+=res[0][i];
	printf("%d\n",ans%mod);
}

5 【hdu 2243】考研路茫茫——单词情结

有N个词根，问长度不超过L的单词中包含词根的数量

mod\(2^{64}\) 相当于开unsigned long long 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int N=35;
int L,n,tot,id[26],fail[N],tag[N],trie[N][26];
unsigned long long ans1,ans2,g[N][N],res[N][N],c[N][N];
queue<int> Q;
char s[6];
void Add()
{
	int len=strlen(s),pre=0;
	for(int i=0;i<len;i++)
	{
		if(trie[pre][s[i]-'a']==-1)
		{
			trie[pre][s[i]-'a']=++tot;
			memset(trie[tot],-1,sizeof(trie[tot]));
			tag[tot]=0;
		}
		pre=trie[pre][s[i]-'a'];
	}
	tag[pre]=1;
}
void Construct()
{
	fail[0]=0;
	for(int i=0;i<26;i++)
	{
		if(trie[0][i]!=-1) fail[trie[0][i]]=0,Q.push(trie[0][i]);
		else trie[0][i]=0;
	}
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		if(tag[fail[x]]) tag[x]=1;
		for(int i=0;i<26;i++)
		{
			if(trie[x][i]!=-1)
			{
				Q.push(trie[x][i]);
				fail[trie[x][i]]=trie[fail[x]][i];
			}
			else trie[x][i]=trie[fail[x]][i];
		}
	}
	memset(g,0,sizeof(g));
	for(int i=0;i<=tot;i++)
	  for(int j=0;j<26;j++)
	    if(!tag[i]&&!tag[trie[i][j]]) g[i][trie[i][j]]++;
	for(int i=0;i<=tot+1;i++)
	  g[i][tot+1]=1;
}
void Multi(unsigned long long a[N][N],unsigned long long b[N][N],int flag,int t)
{
	memset(c,0,sizeof(c));
	for(int i=0;i<=t;i++)
	  for(int j=0;j<=t;j++)
	  	for(int k=0;k<=t;k++)
	      c[i][j]+=a[i][k]*b[k][j];
	if(!flag) memcpy(g,c,sizeof(c));
	else memcpy(res,c,sizeof(c));
}
void power(int b,int t)
{
	memset(res,0,sizeof(res));
	for(int i=0;i<N;i++)  res[i][i]=1;
	for(;b;b>>=1,Multi(g,g,0,t))
	  if(b&1) Multi(res,g,1,t);
}
int main()
{
	while(scanf("%d%d",&n,&L)==2)
	{
		tot=0;tag[0]=0;
		memset(trie[0],-1,sizeof(trie[0]));
		for(int i=1;i<=n;i++)
		  scanf("%s",s),Add();
		Construct();
		power(L,tot+1);
		ans1=0;
		for(int i=0;i<=tot+1;i++)
		  ans1+=res[0][i];
		g[0][0]=26;g[0][1]=0;g[1][0]=g[1][1]=1;
		power(L,1);
		ans2=res[1][0]+res[0][0];
		printf("%llu\n",ans2-ans1);
	}
}

AC自动机