AC自动机+dp.doc

Pku3691DNA repair:给定m个病毒DNA片段，在给一个DNA序列，求最小经过多少次改动可以消去病毒序列。无法则输出-1.
Pku2778DNA，也是给你m个病毒DNA片段，求长度为N的没有病毒序列的种数结果mod100000。
Pku1625，给定字母表E,在给你n个禁止出现子序列，求长度为M的序列有多少种，输出结果。高精度。

PKU3691
#include<iostream>
using namespace std;

const int size = 1003;
const int MAXINT = 1<<30;
int dp[size][size];
char word[24];
char str[size];
struct Node
{
int end,fail,son[4];
void Init()
{
end = 0;
fail = -1;
memset(son, -1, sizeof(son));
}
}node[size];

int node_Num = 0;
int q[size],head,tail;

int Index(char a)
{
switch(a)
{
case 'A':return 0;
case 'G':return 1;
case 'C':return 2;
case 'T':return 3;
}
}

void Insert(char *s)
{
int p = 0;
for(int i=0; s[i]; i++)
{
if (node[p].son[Index(s[i])] == -1)
{
node_Num++;
node[p].son[Index(s[i])] = node_Num;
node[node_Num].Init();
}
if (node[p].end) break;/*危险结点为其子结点不必继续 */
p = node[p].son[Index(s[i])];
}
node[p].end++;
}

void Build_Ac()
{
int temp, p, i;
head = tail = 0;
q[tail++] = 0;
while (head < tail)
{
temp = q[head++];
for (i = 0; i < 4; i++)
if (node[temp].son[i] != -1)
{
if (temp == 0) node[node[temp].son[i]].fail = 0;
else
{
p = node[temp].fail;
while (p != -1)
{
if (node[p].son[i] != -1)
{
node[node[temp].son[i]].fail = node[p].son[i];
/*无此句，wa！*/
if (node[node[p].son[i]].end)
node[node[temp].son[i]].end++;
break;
}
p = node[p].fail;
}
if (p == -1) node[node[temp].son[i]].fail = 0;
}
q[tail++] = node[temp].son[i];
}
}
}

void toMin(int &a, int b)
{
if(a>b||a==-1) a=b;
}

int Done()
{
int i, j, k, Min = MAXINT, tmp;
memset(dp, -1, sizeof(dp));
dp[0][0] = 0;

for (i = 0; str[i]; i++)
for (j = 0; j <= node_Num; j++)
if (dp[i][j] != -1)
{
for (k = 0; k < 4; k++)
{
tmp = j;
while (tmp != -1)
{
if (node[tmp].son[k] != -1)
{
tmp = node[tmp].son[k];
break;
}
tmp = node[tmp].fail;
}
if (tmp == -1) tmp = 0;
if (!node[tmp].end)
toMin(dp[i+1][tmp], dp[i][j]+(Index(str[i])!= k));/*1or0*/
}
}
for (j = 0; j <= node_Num; j++)
if (dp[i][j] != -1 && Min > dp[i][j])
Min = dp[i][j];
return (Min==MAXINT)?-1:Min;
}

int main()
{
int N, i, ans, Case=1;
while (scanf("%d",&N) && N)
{
node_Num = 0;
node[0].Init();

for (i = 0; i < N; i++)
{
scanf("%s",word);
Insert(word);
}
scanf("%s",str);
Build_Ac();
ans = Done();
printf("Case %d: %d\n",Case++, ans);
}
return 0;
}

PKU2778
#include<iostream>
using namespace std;
const int Mod = 100000;
const int size = 120;
__int64 g[size][size];

struct Node
{
int fail,son[4],end;
void Init()
{
fail = -1;
memset(son, -1, sizeof(son));
end = 0;
}
}node[size];

int node_Num = 0;
int q[size], head, tail;

int Index(char a)
{
switch (a)
{
case 'A':return 0;
case 'G':return 1;
case 'C':return 2;
case 'T':return 3;
}
}

void Insert(char *s)
{
int p=0;
for (int i=0; s[i]; i++)
{
if (node[p].end) break;
if (node[p].son[Index(s[i])] == -1)
{
node_Num++;
node[p].son[Index(s[i])] = node_Num;
node[node_Num].Init();
}
p = node[p].son[Index(s[i])];
}
node[p].end++;
}

void Build_Ac()
{
head = tail = 0;
int temp = 0, p = 0, i;
q[tail++] = 0;
while (head < tail)
{
temp = q[head++];
for (i = 0; i < 4; i++)
if (node[temp].son[i] != -1)
{
if (temp == 0) node[node[temp].son[i]].fail = 0;
else
{
p = node[temp].fail;
while (p != -1)
{
if (node[p].son[i] != -1)
{
node[node[temp].son[i]].fail = node[p].son[i];
if (node[node[p].son[i]].end)
node[node[temp].son[i]].end++;
break;
}
p = node[p].fail;
}
if (p == -1) node[node[temp].son[i]].fail = 0;
}
q[tail++] = node[temp].son[i];
}
}
}

void MatrixMul(__int64 b[][size], __int64 c[][size], int sz)
{
int i, j, k;
__int64 temp[size][size] = {0};
for (i = 0; i < sz; i++)
for (j = 0; j < sz; j++)
for (k = 0; k < sz; k++)
{
temp[i][j] += b[i][k]*c[k][j];
if (temp[i][j] >= Mod)
temp[i][j] %= Mod;
}

for (i = 0; i < sz; i++)
for (j = 0; j < sz; j++)
b[i][j] = temp[i][j];
}

void MatrixPow(__int64 tot[][size], __int64 a[][size], int sz, int n)
{
while (n > 0)
{
if (n&1) MatrixMul(tot,a, sz);
MatrixMul(a, a, sz);
n >>= 1;
}
}

int N = 2000000000;
int M;
char word[14];
__int64 tot[size][size];
int main()
{
int i, j;
while (scanf("%d%d", &M, &N) != EOF)
{
node_Num = 0;
node[0].Init();
memset(g, 0, sizeof(g));
for (i = 0; i < M; i++)
{
scanf("%s", word);
Insert(word);
}
Build_Ac();

node_Num++;
for (i = 0; i < node_Num; i++)
if(!node[i].end)
for (j = 0; j < 4; j++)
{
if (node[i].son[j] != -1 && node[node[i].son[j]].end==0)
g[i][node[i].son[j]]++;
else if (node[i].son[j]== -1)
{
if (i==0) g[0][0]++;
else
{
int temp = i;
while (node[temp].son[j]== -1)
{
if (temp==0)break;
temp = node[temp].fail;
}
if(node[temp].son[j] != -1 && node[node[temp].son[j]].end==0)
g[i][node[temp].son[j]]++;
else if (node[temp].son[j]== -1&& temp==0)
g[i][0]++;
}
}
}
memset(tot, 0, sizeof(tot));
for (i = 0; i < node_Num; i++)
tot[i][i] = 1;
MatrixPow(tot, g, node_Num, N);

__int64 ans = 0;
for (i = 0; i < node_Num; i++)
if (node[i].end==0)
{
ans += tot[0][i];
if (ans>=Mod) ans %= Mod;
}
printf("%I64d\n",ans);
}
return 0;
}

8