Reku
0%

AC自动机

Posted on Edited on In Views: Valine:

Recently Peter received m strings as a birthday gift. These strings only consist of lowercase letters. But Peter is not happy, as he hates all of these strings. So he wants to construct a new string of length n and it cannot contain any of the m strings as a substring. Of course,the new string is made up of lowercase letters too. Now he wonders how many strings he can construct. Input On the first line there is only one integer T(T is about 10), representing the number of cases. In each case: there are two integers n, m(n ≤ 1000, m ≤ 50) on the first line followed by m lines, representing the m strings Peter received. Note that the total length of the m strings won’t exceed 500 in each case. Output For each test case, output an integer in one line, which is the number of strings Peter can construct mod 1000000007. Sample Input 1 5 1 aaa Sample Output 11879400

今天集训时候这道题因为不会AC自动机...就没做出来...跌了一大段Rating 其实就是在AC自动机上跑DP，唯一的坑点就是，如果一个点的fail是匹配的话，那这个点也是一个匹配...不过一个好的模板这个情况应该已经考虑到了... 剩下就很简单了...

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#define mod 1000000007
using namespace std;
struct Trie
{
	int next[500010][26],fail[500010],end[500010];
	int root,L;
	int newcode()
	{
		for(int i=0;i<26;i++)
			next[L][i]=-1;
		end[L++]=0;
		return L-1;
	}
	void init()
	{
		L=0;
		root=newcode();
	}
	void insert(char *s)
	{
		int len=strlen(s);
		int now=root;
		for(int i=0;i<len;i++)
		{
			if(next[now][s[i]-'a']==-1)
				next[now][s[i]-'a']=newcode();
			now=next[now][s[i]-'a'];
		}
		end[now]++;
	}
	void build()
	{
		queue<int> Q;
        fail[root] = root;
        for(int i=0;i<26;i++)
        {
            if(next[root][i]==-1)
                next[root][i]=root;
            else
            {
                fail[next[root][i]]=root;
                Q.push(next[root][i]);
            }
        }
        while(!Q.empty())
        {
            int now = Q.front();
            Q.pop();
            for(int i=0;i<26;i++)
            {
                if(next[now][i]==-1)
                {
                    next[now][i]=next[fail[now]][i];
                }
                else
                {
                    fail[next[now][i]]=next[fail[now]][i];
                    end[next[now][i]]|=end[fail[next[now][i]]];
                    Q.push(next[now][i]);
                }
            }
        }
	}
	int query(int n)
	{
		int now=root;
		int f[2][250010]={};
		f[0][now]=1;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<=L;j++)
			{
				for(int k=0;k<26;k++)
				{
					if(end[next[j][k]]==0)	f[(i+1)%2][next[j][k]]+=f[i%2][j];
					f[(i+1)%2][next[j][k]]%=mod;
				}
				f[i%2][j]=0;
			}
		}
		int res=0;
		for(int j=0;j<=L;j++)
		{
			res+=f[n%2][j];
			res%=mod;
		}
		return res;
	}
	void debug()
    {
        for(int i = 0;i < L;i++)
        {
            printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],end[i]);
            for(int j = 0;j < 26;j++)
                printf("%2d",next[i][j]);
            printf("]\n");
        }
    }
} tr;
void work()
{
	tr.init();
	int n,m;
	char s[510];
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%s",s);
		tr.insert(s);
	}
	tr.build();
	printf("%d\n",tr.query(n));
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--) work();
	return 0;
}

http://acm.hdu.edu.cn/showproblem.php?pid=2222 学习的时候刷了一道杭电oj的模板题

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
struct Trie
{
    int next[500010][26],fail[500010],end[500010];
    int root,L;
    int newcode()
    {
        for(int i=0;i<26;i++)
            next[L][i]=-1;
        end[L++]=0;
        return L-1;
    }
    void init()
    {
        L=0;
        root=newcode();
    }
    void insert(char *s)
    {
        int len=strlen(s);
        int now=root;
        for(int i=0;i<len;i++)
        {
            if(next[now][s[i]-'a']==-1)
                next[now][s[i]-'a']=newcode();
            now=next[now][s[i]-'a'];
        }
        end[now]++;
    }
    void build()
    {
        queue<int> Q;
        fail[root] = root;
        for(int i=0;i<26;i++)
        {
            if(next[root][i]==-1)
                next[root][i]=root;
            else
            {
                fail[next[root][i]]=root;
                Q.push(next[root][i]);
            }
        }
        while(!Q.empty())
        {
            int now = Q.front();
            Q.pop();
            for(int i=0;i<26;i++)
            {
                if(next[now][i]==-1)
                {
                    next[now][i]=next[fail[now]][i];
                }
                else
                {
                    fail[next[now][i]]=next[fail[now]][i];
                    Q.push(next[now][i]);
                }
            }
        }
    }
    int query(char* s)
    {
        int len=strlen(s);
        int now=root;
        int res=0;
        for(int i=0;i<len;i++)
        {
            now=next[now][s[i]-'a'];
            int temp=now;
            while(temp!=root)
            {
                res+=end[temp];
                end[temp]=0;
                temp=fail[temp];
            }
        }
        return res;
    }
    void debug()
    {
        for(int i = 0;i < L;i++)
        {
            printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],end[i]);
            for(int j = 0;j < 26;j++)
                printf("%2d",next[i][j]);
            printf("]\n");
        }
    }
} tr;
void work()
{
    tr.init();
    int n;
    char s[1000010];
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s);
        tr.insert(s);
    }
    tr.build();
    scanf("%s",s);
    printf("%d\n",tr.query(s));
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--) work();
    return 0;
}

http://www.lydsy.com/JudgeOnline/problem.php?id=1030 f[i][j][0]代表长度为i，在自动机上编号j的位置，在之前没有匹配到的单词的情况数。 f[i][j][1]代表长度为i，在自动机上编号j的位置，在之前已经匹配过单词的情况数。

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<bits/stdc++.h>
#define mod 10007
using namespace std;
int n,m;
char s[110]={};
int f[110][6010][2]={};
struct Trie
{
	int next[6010][26],fail[6010],end[6010];
	int root,L;
	int newcode()
	{
		for(int i=0;i<26;i++)
		{
			next[L][i]=-1;
		}
		end[L++]=0;
		return L-1;
	}
	void init()
	{
		L=0;
		root=newcode();
	}
	void insert(char *s)
	{
		int len=strlen(s);
		int now=root;
		for(int i=0;i<len;i++)
		{
			if(next[now][s[i]-'A']==-1)
			{
				next[now][s[i]-'A']=newcode();
			}
			now=next[now][s[i]-'A'];
		}
		end[now]++;
	}
	void build()
	{
		queue<int> Q;
		fail[root]=root;
		for(int i=0;i<26;i++)
		{
			if(next[root][i]==-1)
			{
				next[root][i]=root;	
			}
			else
			{
				fail[next[root][i]]=root;
				Q.push(next[root][i]);
			}
		}
		while(!Q.empty())
		{
			int now=Q.front();
			Q.pop();
			for(int i=0;i<26;i++)
			{
				if(next[now][i]==-1)
				{
					next[now][i]=next[fail[now]][i];
				}
				else
				{
					fail[next[now][i]]=next[fail[now]][i];
					end[next[now][i]]|=end[fail[next[now][i]]];
					Q.push(next[now][i]);
				}
			}
		}
	}
	int query(int m)
	{
		f[0][root][0]=1;
		for (int i=0;i<m;i++)
		{
			for(int j=0;j<L;j++)
			{
				for(int k=0;k<26;k++)
				{
					f[i+1][next[j][k]][0]+=f[i][j][0];
					f[i+1][next[j][k]][0]%=mod;
					f[i+1][next[j][k]][1]+=f[i][j][1];
					f[i+1][next[j][k]][1]%=mod;
				}
			}
			for(int j=0;j<L;j++)
			{
				if(end[j])
				{
					f[i+1][j][1]+=f[i+1][j][0];
					f[i+1][j][1]%=mod;
					f[i+1][j][0]=0;
				}
			}
		}
		int ans=0;
		for(int i=0;i<L;i++)
		{
			ans+=f[m][i][1];
			ans%=mod;
		}
		return ans;
	}
} tr;
int main()
{
	tr.init();
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s);
		tr.insert(s);
	}
	tr.build();
	printf("%d",tr.query(m));
	return 0;
}