POJ 2778 DNA Sequence 长度为n且不含m种模式串的字符串种数

题目来源：POJ 2778 DNA Sequence

题意：给你m个字符串 求出长度为n 并且不包含m个模式串的任何一个的文本串的数量

思路：有一个经典的矩阵题目：给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数

这里的k步就是字符串的长度 点就是AC自动机上的节点 2点之间有路必须满足2个节点都不是禁止节点   求的长度为n 然后次矩阵快速幂即可

需要透彻理解AC自动机 状态图就是一个转移过程

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

const int maxnode = 11*11;
const int size = 4;
int ch[maxnode][size];
int val[maxnode];
int f[maxnode];
int sz;

const long long mod = 100000;
struct Mat
{
    long long a[maxnode][maxnode];
};
Mat A, B, C;
void init()
{
	sz = 1;
	memset(ch[0], 0, sizeof(ch[0]));
}
int idx(char c)
{
	if(c == ‘A‘)
		return 0;
	if(c == ‘T‘)
		return 1;
	if(c == ‘C‘)
		return 2;
	if(c == ‘G‘)
		return 3;
}
void insert(char *s, int v)
{
	int u = 0, n = strlen(s);
	for(int i = 0; i < n; i++)
	{
		int c = idx(s[i]);
		if(!ch[u][c])
		{
			memset(ch[sz], 0, sizeof(ch[sz]));
			val[sz] = 0;
			ch[u][c] = sz++;
		}
		u = ch[u][c];
	}
	val[u] = 1;
}
void getFail()
{
	queue <int> q;
	f[0] = 0;
	for(int c = 0; c < 4; c++)
	{
		int u = ch[0][c];
		if(u)
		{
			f[u] = 0;
			q.push(u);
		}
	}
	while(!q.empty())
	{
		int r = q.front(); q.pop();
		
		for(int c = 0; c < 4; c++)
		{
			int u = ch[r][c];
			if(!u)
			{
				ch[r][c] = ch[f[r]][c];
				continue;
			}
			q.push(u);
			int v = f[r];
			while(v && !ch[v][c])
				v = f[v];
			f[u] = ch[v][c];
			val[u] |= val[f[u]];
		}
	}
}

Mat get(Mat x, Mat y)
{
    Mat z;
    memset(z.a, 0, sizeof(z.a));
    for(int i = 0; i < sz; i++)
        for(int j = 0; j < sz; j++)
            for(int k = 0; k < sz; k++)
            {
                z.a[i][j] += x.a[i][k] * y.a[k][j];
                z.a[i][j] %= mod;
            }
    return z;
}
void Mat_pow(int x)
{
    while(x)
    {
        if(x&1)
            B = get(B, A);
        A = get(A, A);
        x >>= 1;
    }
}
int main()
{
	int n, m;
	while(scanf("%d %d", &n, &m) != EOF)
	{
		init();
		for(int i = 0; i < n; i++)
		{
			char s[12];
			scanf("%s", s);
			insert(s, 1);
		}
		getFail();
		memset(A.a, 0, sizeof(A.a));
		memset(B.a, 0, sizeof(B.a));
		for(int i = 0; i < sz; i++)
		{
			if(val[sz])
				continue;
			for(int j = 0; j < 4; j++)
			{
				if(val[ch[i][j]])
					continue;
				A.a[i][ch[i][j]]++;
			}
			
		}
		for(int i = 0; i < sz; i++)
			B.a[i][i] = 1;
		Mat_pow(m);

		long long ans = 0;
		for(int i = 0; i < sz; i++)
		{
			ans += B.a[0][i];
			ans %= mod;
		}
		printf("%lld\n", ans);
	}
	return 0;
}

POJ 2778 DNA Sequence 长度为n且不含m种模式串的字符串种数,布布扣,bubuko.com

POJ 2778 DNA Sequence 长度为n且不含m种模式串的字符串种数

原文：http://blog.csdn.net/u011686226/article/details/24061605