HDU 2896

别把num设成-1…因为有多个母串…

POJ 2778

题意：有m种DNA序列是有疾病的，问有多少种长度为n的DNA序列不包含任何一种有疾病的DNA序列。（仅含A,T,C,G四个字符）

解题思路：

AC自动机+矩阵快速幂

http://blog.csdn.net/morgan_xww/article/details/7834801

这里涉及到用Trie图构造邻接矩阵…

于是补了一下Trie图的构建…

http://www.cppblog.com/menjitianya/archive/2014/07/10/207604.html

这里还有一个知识点：矩阵A^m所代表的意义就是从点与点之间走m步能够到达的方案总数。

http://blog.csdn.net/WT_cnyali/article/details/69803030

HDU 2243

题意：给定n个单词，求长度不大于m的字符串中所有含给定单词的字符串的个数 。

解题思路：

整体和上题相似，即所有情况再减去上题求的情况即可。

将运算过程中的变量和矩阵的元素定义为unsigned __int64，就能实现自动对2^64自动取MOD。注意输出是%I64u。

HDU 2457

题意：已知一个DNA串和一些病毒DNA序列，求出最少改变DNA串中多少个字符，能使得串中不包含任意一个病毒序列。

解题思路：Trie图+DP。
先构造Trie图，这里要注意如果fail指针指向危险子串的本身也危险，
if(temp->child[i]->fail->num==1)//注意：fail指针指向危险子串的本身也危险
temp->child[i]->num=1;
之后就是DP，f[i][j]表示匹配到原串第i个字符时，在AC自动机的j号节点时没有病毒串的最小花费。转移的时候有三种情况：1.转移出病毒串，这个时候直接continue。2.转移与原串相符，这个时候直接将数值转移过去。3.转移与原串不符，这个时候转移数值之后还要+1，再在dp[len][i]中找到最小值。

   for(int i=0;i<=len;i++)
    for(int j=0;j<sum;j++)
        dp[i][j]=INF;
    dp[0][0]=0;
    for(int i=1;i<=len;i++)
    for(int j=0;j<sum;j++)
    if(dp[i-1][j]<INF)//不是从病毒串转移的
    {
        for(int k=0;k<4;k++)
        {
            if(Trie[j].child[k]->num==0)//不是一个单词的结尾
            {
                p=Trie[j].child[k];
                //转移与原串相符，这个时候直接将数值转移过去。转移与原串不符，这个时候转移数值之后还要+1。
                dp[i][p->idd]=min(dp[i][p->idd],dp[i-1][j]+(bh(str[i-1])!=k));
            }
        }
    }
    int ans=INF;
    for(int i=0;i<sum;i++)
    {
        if(Trie[i].num==0&&dp[len][i]<ans)
            ans=dp[len][i];
    }
    if(ans==INF)ans=-1;