POJ 2778 (AC自动机+矩阵乘法)

POJ 2778 DNA Sequence

Problem : 给m个只含有（A,G,C,T）的模式串(m <= 10, len <=10), 询问所有长度为n的只含有(A,G,C,T)的串中有多少个不含有模式串的串。(n<=2000000000)

Solution :首先对所有模式串建立AC自动机。然后dp[i][j]表示长度为i，走到AC自动机的节点j这样的字符串满足条件的个数有多少，用AC自动机的边写出状态转移方程然后用矩阵快速幂加速运算。

#include <iostream>

#include <string>

#include <queue>

using namespace std;

const int N = 208;

const int mo = 100000;

int id[128];

struct Matrix

{

	int n;

	int a[N][N];

	Matrix(int n_, int p)

	{

		n = n_;

		for (int i = 0; i < n; ++i)

			for (int j = 0; j < n; ++j)

			{

				a[i][j] = 0;

				if (i == j) a[i][j] = p;

			}

	}

	friend Matrix operator *(Matrix A, Matrix B)

	{

		Matrix C(A.n, 0);

		for (int i = 0; i < A.n; ++i)

			for (int j = 0; j < A.n; ++j)

				for (int k = 0; k < A.n; k++)

					C.a[i][j] = (C.a[i][j] + 1ll * A.a[i][k] * B.a[k][j] % mo) % mo;

		return C;

	}

	void print()

	{

		for (int i = 0; i < n; ++i)

		{

			for (int j = 0; j < n; ++j) cout << a[i][j] << " ";

			cout << endl;

		}

	}

};

struct AC_Automan

{

	int next[N][4];

	int fail[N];

	int cnt[N];

	int root, tot;

	int newnode()

	{

		for (int i = 0; i <= 3; ++i) next[tot][i] = -1;

		fail[tot] = cnt[tot] = -1;

		return tot++;

	}

	void clear()

	{

		tot = 0;

		root = newnode();

	}

	void insert(const string &s)

	{

		int p = root;

		for (int i = 0, len = s.length(); i < len; ++i)

		{

			if (next[p][id[s[i]]] == -1) next[p][id[s[i]]] = newnode();

			p = next[p][id[s[i]]];

		}

		cnt[p] = 1;

	}

	void build()

	{

		queue <int> Q;

		Q.push(root);

		while (!Q.empty())

		{

			int p = Q.front(); Q.pop();

			for (int i = 0; i < 4; ++i)

			{

				if (~next[p][i])

				{

					if (p == root) fail[next[p][i]] = root;

					else fail[next[p][i]] = next[fail[p]][i];

					Q.push(next[p][i]);

				}

				else

				{

					if (p == root) next[p][i] = root;

					else next[p][i] = next[fail[p]][i];

				}

			}

		}

	}

	Matrix power(Matrix A, int y)

	{

		Matrix B(tot, 1);

		while (y)

		{

			if (y & 1) B = B * A;

			A = A * A;

			y >>= 1;

		}

		return B;

	}

	void solve(int num)

	{

		Matrix A(tot, 0);

		for (int i = 0; i <= tot; ++i)

		{

			for (int j = 0; j < 4; ++j)

			{

				int flag = 1;

				for (int temp = next[i][j]; temp != root; temp = fail[temp])

				{

					if (~cnt[temp]) flag = 0;

				}

				A.a[i][next[i][j]] += flag;

			}

		}

		A = power(A, num);

		int ans = 0;

		for (int i = 0; i < tot; ++i) ans = (ans + A.a[0][i]) % mo;

		cout << ans << endl;

	}

}ac;

int main()

{

	cin.sync_with_stdio(0);

	id['A'] = 0; id['G'] = 1; id['C'] = 2; id['T'] = 3;

	int m, n;

	while (cin >> m >> n)

	{

		ac.clear();

		for (int i = 1; i <= m; ++i)

		{

			string s; cin >> s;

			ac.insert(s);

		}

		ac.build();

		ac.solve(n);

	}

}

巴特西

POJ 2778 (AC自动机+矩阵乘法)

POJ 2778 DNA Sequence

最新文章

热门文章