POJ 2778 AC自动机 - c++编程基础

这题还是挺经典的

首先的话，是建立自动机的过程。其实就是一个状态的转移，看一个字典树中的某子串加上一个字母是否会变成一个非法的串，然后都给标记起来。

最后就看有多少种状态，就建立多大的矩阵，对某种状态，如果加上一个字母后是合法的，就把表示状态可以转移。对应的矩阵中的位置就++

然后就是矩阵乘了，乘了k次后的矩阵x[i][j] 就表示从i状态到j状态路径转移长度为k的个数，那最后的结果就是从0状态到所有状态的和了

需要注意的是取模运算耗费的时间很大，能尽量减少就减少这种操作。

[cpp]
include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-5
#define MAXN 155
#define MAXM 40000
#define INF 1000000001
#define lch(x) x<<1
#define rch(x) x<<1|1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
int h[155];
int n, m, e;
long long mat[MAXN][MAXN], ans[MAXN][MAXN];
struct Trie
{
int next[4];
int fail, flag;
void init ()
{
memset(next, 0, sizeof(next));
fail = -1;
flag = 0;
}
} trie[MAXM];
void init()
{
for(int i = 0; i < MAXM; i++) trie[i].init();
e = 0;
memset(mat, 0, sizeof(mat));
memset(ans, 0, sizeof(ans));
}
void make_trie (char *str)
{
int i = 0, index, u = 0;
while(str[i])
{
index = h[str[i]];
if(!trie[u].next[index]) trie[u].next[index] = ++e;
u = trie[u].next[index];
i++;
}
trie[u].flag = 1;
}
int q[MAXM];
void make_ac_automation()
{
int h = 0, t = 0;
q[t++] = 0;
while(h < t)
{
int u = q[h++], v, j;
for(int i = 0; i < 4; i++)
{
if(trie[u].next[i])
{
v = trie[u].next[i];
j = trie[u].fail;
while(j != -1 && !trie[j].next[i]) j = trie[j].fail;
if(j == -1) trie[v].fail = 0;
else
{
trie[v].fail = trie[j].next[i];
trie[v].flag |= trie[trie[v].fail].flag;
}
q[t++] = v;
}
else
{
j = trie[u].fail;
while(j != -1 && !trie[j].next[i]) j = trie[j].fail;
if(j == -1) trie[u].next[i] = 0;
else trie[u].next[i] = trie[j].next[i];
}
}
}
}
long long z[MAXN][MAXN];
long long mod = 100000;
void multiply(long long x[MAXN][MAXN], long long y[MAXN][MAXN])
{
for(int i = 0; i <= e; i++)
{
for(int j = 0; j <= e; j++)
{
z[i][j] = 0;
for(int k = 0; k <= e; k++)
z[i][j] = z[i][j] + x[i][k] * y[k][j];
z[i][j] %= mod;
}
}
for(int i = 0; i <= e; i++)
for(int j = 0; j <= e; j++)
y[i][j] = z[i][j];
}
int main()
{
init();
h['A'] = 0, h['T'] = 1, h['G'] = 2, h['C'] = 3;
scanf("%d%d", &m, &n);
char str[25];
for(int i = 0; i < m; i++)
{
scanf("%s", str);
make_trie(str);
}
make_ac_automation();
for(int i = 0; i <= e; i++)
if(trie[i].flag == 0)
for(int j = 0; j < 4; j++)
if(trie[trie[i].next[j]].flag == 0)
mat[i][trie[i].next[j]]++;
for(int i = 0; i <= e; i++) ans[i][i] = 1;
while(n)
{
if(n & 1) multiply(mat, ans);
multiply(mat, mat);
n >>= 1;
}
long long res = 0;
for(int i = 0; i <= e; i++) res = res + ans[0][i];
printf("%I64d\n", res % mod);
return 0;
}

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-5
#define MAXN 155
#define MAXM 40000
#define INF 1000000001
#define lch(x) x<<1
#define rch(x) x<<1|1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
int h[155];
int n, m, e;
long long mat[MAXN][MAXN], ans[MAXN][MAXN];
struct Trie
{
int next

POJ 2778 AC自动机 (一)