Posts Tagged ‘AC自动机’

POJ 2778 DNA Sequence

Posted in PKU OJ on 四月 24th, 2010 by 纳米 – Be the first to comment

2010-04-17，阅读题目
2010-04-23，因前一题一直拖着，开始阅读题解，学习Trie、AC自动机等，Code。Code完毕发现POJ挂掉。
2010-04-24，发现不是POJ挂，而是域名解析出问题，立刻换8.8.8.8。第一次提交，WA，第二次AC。

解题报告：
参考POJ 2778 DNA Sequence [AC自动机+矩阵递推]、十个利用矩阵乘法解决的经典题目

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176

#include <stdio.h>
#include <string.h>
 
const int maxm = 11, maxstrlen = 13, maxn = 103;
int n, m, k, answer;
char virus[maxm][maxstrlen];
 
struct trieNode {
	int next[4], pre;
	bool mark;
	trieNode() {
		memset(next,0,sizeof(next));
		pre = mark = 0;
	}
} trie[maxn];
 
class Matrix {
	private:
		void set_unit();
	public:
		int n, m, arr[maxn][maxn];
		Matrix();
		Matrix(int, int);
		Matrix power(int);
		Matrix operator * (const Matrix);
		int sum();
} fsm;
 
void Matrix::set_unit() {
	for (int i = 0; i < n; ++i)
		arr[i][i] = 1;
}
 
Matrix::Matrix() {
	memset(arr, 0, sizeof(arr));
}
 
Matrix::Matrix(int n0, int m0) {
	n = n0, m = m0;
	memset(arr, 0, sizeof(arr));
}
 
Matrix Matrix::power(int k) {
	Matrix res(n, m);
	res.set_unit();
	while (k) {
		if (k & 1)
			res = res * (*this);
		(*this) = (*this) * (*this);
		k >>= 1;
	}
	return res;
}
 
Matrix Matrix::operator * (const Matrix x) {
	Matrix res(n, x.m);
	for (int i = 0; i < res.n; ++i)
		for (int j = 0; j < res.m; ++j)
			for (int k = 0; k < m; ++k)
				res.arr[i][j] += (int)((long long)arr[i][k] * (long long)x.arr[k][j] % (long long)100000);
	return res;
}
 
int Matrix::sum() {
	int res = 0;
	for (int j = 0; j < m; ++j)
		res = (res + arr[0][j]) % 100000;
	return res;
}
 
int input() {
	scanf("%d%d", &m, &k);
	for (int i = 1; i <= m; ++i)
		scanf("%s", virus[i]);
	return 0;
}
 
bool substr(char str1[], char str2[]) {
	int len1 = strlen(str1), len2 = strlen(str2);
	bool is_ok = false;
	for (int i = 0; i + len2 <= len1 && !is_ok; ++i) {
		is_ok = true;
		for (int j = 0; j < len2 && is_ok; ++j)
			is_ok = str1[i+j] == str2[j];
	}
	return is_ok;
}
 
int num(char ch) {
	switch (ch) {
		case 'A' : return 0;
		case 'C' : return 1;
		case 'T' : return 2;
		case 'G' : return 3;
	}
	return 0;
}
 
int build_trie() {
	bool del[maxm] = {0};
	for (int i = 1; i <= m; ++i)
		for (int j = 1; j <= m && !del[i]; ++j)
			del[i] = i != j && !del[j] && substr(virus[i], virus[j]);
	n = 0;
	for (int i = 1; i <= m; ++i)
		if (!del[i]) {
			int cur = 0;
			for (int j = 0; j < (int)strlen(virus[i]); ++j) {
				if (!trie[cur].next[num(virus[i][j])])
					trie[cur].next[num(virus[i][j])] = ++n;
				cur = trie[cur].next[num(virus[i][j])];
			}
			trie[cur].mark = true;
		}
 
	int q[maxn], head = -1, last = -1;
	for (int i = 0; i < 4; ++i)
		if (trie[0].next[i])
			q[++last] = trie[0].next[i];
	while (head < last) {
		int t = q[++head];
		for (int i = 0; i < 4; ++i)
			if (int cur = trie[t].next[i]) {
				int p = trie[t].pre;
				while (p && !trie[p].next[i])
					p = trie[p].pre;
				trie[cur].pre = trie[p].next[i];
				q[++last] = cur;
			}
	}
	return 0;
}
 
int calc_bfm(int cur) {
	for (int i = 0; i < 4; ++i) {
		int p = cur;
		while (p && !trie[p].next[i])
			p = trie[p].pre;
		p = trie[p].next[i];
		if (p) {
			if (!trie[p].mark)
				++fsm.arr[cur][p];
		} else {
			++fsm.arr[cur][0];
		}
	}
	return 0;
}
 
int build_bfm() {
	fsm.n = fsm.m = n + 1;
	for (int i = 0; i <= n; ++i)
		if (!trie[i].mark)
			calc_bfm(i);
	return 0;
}
 
int work() {
	fsm = fsm.power(k);
	answer = fsm.sum();
	return 0;
}
 
int output() {
	printf("%d\n", answer);
	return 0;
}
 
int main() {
	input();
	build_trie();
	build_bfm();
	work();
	output();
	return 0;
}