特色栏目：服务器安全 Linux 批处理 Linux安全 Mysql Mssql Access 下载中心

AC自动机初步总结

来源：互联网作者：佚名时间：2015-09-25 05:40

AC自动机总结 AC自动机在解决字符串匹配，尤其是多串处理的问题上，表现出了强大的能力。 AC自动机的建立是在trie树的基础之上，我们为每个节点i都找到一个节点j，节点j满足从根到节点j形成的字符串是从根到节点i形成的字符串的最长后缀。这样，如果

AC自动机总结

AC自动机在解决字符串匹配，尤其是多串处理的问题上，表现出了强大的能力。

AC自动机的建立是在trie树的基础之上，我们为每个节点i都找到一个节点j，节点j满足从根到节点j形成的字符串是从根到节点i形成的字符串的最长后缀。这样，如果我们从树中行走到i时发现走不下去了，我们就可以跳到j处，继续走，这是就相当于我们在根处走了几个圈后面从根处走到了j节点（因为从根到j的串在从根到i中出现过而且是后缀）。为了方便，也为了自动机的完美，更是为了快捷，因此我们将trie的指针都建立出来，如果第i个节点有从a出发的边，那么正好，如果没有，我们就让i点从a出发的边指向j点从a出发的边，至于j点有没有从a出发的边，那是j点的事儿了，这样就产生了递推的关系，从根到叶子宽搜递推一边即可。

此外，最近写的数据结构很多都用类来写，这样分装以后就比一堆函数放在一起给人感觉更舒服。也更容易移植，重用。下面的代码有的是函数形式的，有的是类形式是的。

下面是一些例题：

首先是字符串查询，在一个文本中查找一些子串是否出现过之类的信息，这也是自动机的基本应用。

第一部分，字符串查找

第一题：

http://acm.hdu.edu.cn/showproblem.php?pid=2222

Keywords Search

最裸的自动机查询题目，找一个文本中包含多少子串，可以测试模板。只要记住如果i节点的fail指针指向的节点j也是危险节点，那么走到i的时候也应该把j节点的相关信息记录下来，因为从根走到i也就包含和从根做到j的情况。具体怎么记录，常用的方法是直接累计，按位标记，回溯的查找。具体视题目要求而定。有时也可在宽搜序列上从后向前累积计算。这个题就是直接累计个数就可以了，在递推求fail指针是就可递推下来。

code：

#include <stdio.h>
#include <string.h>

struct NODE{
    int next[26];
    int suffix;
    int falg;
    int father;
} trie[255555];
int ad;
char T[1000010];
int queue[255555], boo[255555];

void insert(){
    int q = 0;
    for(int i = 0; T[i] != '\0'; i ++){
        if(trie[q].next[T[i] - 'a'] == -1){
            trie[q].next[T[i] - 'a'] = ad;
            trie[ad ++].father = q;
        }
        q = trie[q].next[T[i] - 'a'];
    }
    trie[q].falg == -1 ? trie[q].falg = 1 : trie[q].falg ++;
}

void Get_trie_map(){
    int head , tail, i, opt, g, j;
    memset(boo, 0, sizeof(boo));
    head = tail = 0;
    trie[0].suffix = 0;
    boo[0] = 1;
    for(i = 0; i < 26; i ++)
        if(trie[0].next[i] == -1) trie[0].next[i] = 0;
        else trie[trie[0].next[i]].suffix = 0;
    queue[tail ++] = 0;
    while(head < tail){
        opt = queue[head ++]; 
        for(i = 0; i < 26; i ++) 
            if(trie[opt].next[i] > opt && boo[trie[opt].next[i]] == 0){
                queue[tail ++] = g = trie[opt].next[i];
                boo[g] = 1;
                if(trie[g].suffix == -1) trie[g].suffix = trie[trie[opt].suffix].next[i];
                for(j = 0; j < 26; j ++)
                    if(trie[g].next[j] == -1) trie[g].next[j] = trie[trie[g].suffix].next[j];
            }
    }
}

void Built_trie(int M){
    int i;
    ad = 1;
    memset(trie, -1, sizeof(trie));
    for(i = 0; i < M; i ++){
        scanf("%s", T);
        insert();
    }
    Get_trie_map();
}

int Find(){
    int i, q = 0, ans = 0, p, t;
    for(i = 0; T[i] != '\0'; i ++){
        q = trie[q].next[T[i] - 'a'];
        if(trie[q].falg > 0){
            ans += trie[q].falg;
            trie[q].falg = 0;
            for(p = q; p > 0; p = trie[p].father)
                for(t = trie[p].suffix; trie[t].falg > 0; t = trie[t].suffix){
                    ans += trie[t].falg;
                    trie[t].falg = 0;
                }
        }
    }
    return ans;
}

int main(){
    int M, i, n;
    scanf("%d", &n);
    while(n --){
        scanf("%d", &M);
        Built_trie(M);
        scanf("%s", T);
        printf("%d\n", Find());
    }
    return 0;
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

第二题：

http://acm.hdu.edu.cn/showproblem.php?pid=2896

病毒侵袭

找一个文本中出现了那些子串，由于子串个数500，所以不好使用位压缩，只能是回溯的去寻找，这是在每个节点增加一个标记域标记他的后缀节点是否包含子串可加速

code：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 510
#define maxnl 210
#define maxm 1010
#define maxml 10010
#define size 128

int clude[maxn], tot, ans;

struct automatonNode{
    bool fake;
    int real;
    automatonNode* next[size], *fail;
    void clear(){
        for(int i = 0; i < size; ++ i) this->next[i] = NULL;
        this->real = this->fake = 0;
    }
};

struct automaton{
    automatonNode* root, * link;
    int ad;
    automaton(){ link = new automatonNode[maxn * maxnl]; }
    ~automaton(){ delete[] link; }
    /* 初始化自动机的初始结点 */
    void clear(){
        ad = 0;
        root = &(link[ad++]);
        root->clear();
        root->fail = root;
    }
    /* 向树中插入字符串 */
    void insert(char* st, int id){
        automatonNode* rt = this->root;
        for(int i = 0; st[i] != '\0'; ++ i){
            if(rt->next[st[i]] == NULL){
                rt->next[st[i]] = &link[ad ++];
                rt->next[st[i]]->clear();
            }
            rt = rt->next[st[i]];
        }
        rt->real = id;
    }
    /* 建立自动机 */
    void built(){
        automatonNode** queue;
        queue = new automatonNode*[maxn * maxnl];
        int head = 0, tail = 0;
        queue[tail ++] = this->root;
        while(head < tail){
            automatonNode* fa;
            fa = queue[head ++];
            for(int i = 0; i < size; ++ i){
                if(fa->next[i] == NULL) fa->next[i] = (fa == root ? (fa) : (fa->fail->next[i]));
                else{
                    fa->next[i]->fail = (fa == root) ? fa : fa->fail->next[i];
                    fa->next[i]->fake = fa->fail->next[i]->fake;
                    queue[tail ++] = fa->next[i];
                }
            }
        }
        delete[] queue;
    }
    /* 查找包含的串 */
    void search(char *st){
        automatonNode* rt = this->root;
        tot = 0;
        memset(clude, 0, sizeof(clude));
        for(int i = 0; st[i] != '\0'; ++ i){
            rt = rt->next[st[i]];  
            if(rt->real) clude[tot ++] = rt->real;
            while(rt->fake){
                if(rt->real) clude[tot ++] = rt->real;
                rt = rt->fail;
            }
        }
    }
    /* 输出答案 */
    void print(int i){
        if(!tot) return;
        ans ++;
        sort(clude, clude + tot);
        printf("web %d:", i);
        for(int i = 0; i < tot; ++ i){ printf(" %d", clude[i]); }
        printf("\n");
    }
};

int main(){
    int n, m;
    char str[maxml];
    automaton trie;
    while(~scanf("%d\n", &n)){
        trie.clear();
        for(int i = 0; i < n; ++ i){
            gets(str);
            trie.insert(str, i + 1);
        }
        trie.built();
        scanf("%d\n", &m);
        for(int i = 0; i < m; ++ i){
            gets(str);
            trie.search(str);
            trie.print(i + 1);
        }
        printf("total: %d\n", ans);
    }
    return 0;
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

第三题：

http://acm.hdu.edu.cn/showproblem.php?pid=3065

病毒侵袭持续中

在文本中查找每个子串出现的次数，和上个题一样，只是开个数组记录下个数就可以个了。

模式串只有26个字母，而文本是128，这个不用管，遇到不是那26个里的字符，直接让树中的指针跳到根节点就可以了。

code：

/*
    hdu2896  AC自动机解字符串匹配
*/

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

#define maxn 1010
#define maxnl 55
#define maxm 2000010
#define size 26

char str[maxm], pan[maxn][maxnl];
int ans[maxn];

struct automatonNode{
    int real;
    bool fake;
    automatonNode* next[size], * fail;
    void clear(){ 
        for(int i = 0; i < size; ++ i) next[i] = NULL; 
        real = fake = 0;
    }
};

struct automaton{
    automatonNode * root, * link;
    int ad;
    automaton(){ link = new automatonNode[maxn * maxnl]; }
    ~automaton(){ delete[] link; }
    void clear(){
        ad = 0;
        root = &link[ad ++];
        root->clear();
        root->fail = root;
    }
    int cg(char ch){ return ch - 'A'; }
    /* 向树中插入节点 */
    void insert(char *st, int id ){
        automatonNode* rt = root;
        for(int i = 0; st[i] != '\0'; ++ i){
            if(rt->next[cg(st[i])] == NULL){
                rt->next[cg(st[i])] = &link[ad ++];
                rt->next[cg(st[i])]->clear();
            }
            rt = rt->next[cg(st[i])];
        }
        rt->real = id;;
    }
    /* 建立自动机 */
    void built(){
        automatonNode** queue;
        queue = new automatonNode*[maxn * maxnl];
        int head = 0, tail = 0;
        queue[tail ++] = root;
        while(head < tail){
            automatonNode* fa = queue[head ++];
            for(int i = 0; i < size; ++ i){
                if(fa->next[i] == NULL){ fa->next[i] = (fa == root) ? (fa) : (fa->fail->next[i]); }
                else{
                    fa->next[i]->fail = (fa == root) ? (fa) : (fa->fail->next[i]);
                    fa->next[i]->fake = fa->fail->fake;
                    queue[tail ++] = fa->next[i];
                }
            }
        }
    }
    /* 判断字符范围 */
    bool ineare(char ch){
        return ch >= 'A' && ch <= 'Z';
    }
    /* 查找TXT包含每个子串的个数 */
    void search(char *st){
        memset(ans, 0, sizeof(ans));
        automatonNode* rt = root;
        for(int i = 0; st[i] != '\0'; ++ i){
            if(!ineare(st[i])) rt = root;
            else{
                rt = rt->next[cg(st[i])];
                if(rt->real) ans[rt->real] ++;
                while(rt->fake){
                    if(rt->real) ans[rt->real] ++;
                    rt = rt->fail;
                }
            }
        }
    }
    /* 输出包含每个串的个数 */
    void print(int n){
        for(int i = 0; i < n; ++ i){
            if(ans[i + 1]) printf("%s: %d\n", pan[i], ans[i + 1]);
        }
    }
};

int main(){
    int n;
    automaton trie;
    while(~scanf("%d", &n)){
        trie.clear();
        for(int i = 0; i < n; ++ i){
            scanf("%s", pan[i]);
            trie.insert(pan[i], i + 1);
        }
        trie.built();
        getchar();
        gets(str);
        trie.search(str);
        trie.print(n);
    }
    return 0;
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

第二部分是自动机和矩阵结合的题目。

题目：http://acm.hdu.edu.cn/showproblem.php?pid=2243

考研路茫茫——单词情结

给出n个串，求至少包含一个串的长度不操过L的串的个数。利用图的n次幂表示两点间路径长度是n的个数。再利用二分求幂的前n项和。

危险节点是不能走到的，因此在建立矩阵时我们直接将危险节点和危险节点的孩子节点截掉。

详细见：http://blog.csdn.net/threedonkey/article/details/7384031

第三部分自动机Dp。

自动机dp的题目都是很相似的，就是dp【使用了什么】【到达那个状态】达的最好效果是什么。下面看具体的例子：

第一题：

http://acm.hdu.edu.cn/showproblem.php?pid=2825

Wireless Password

给出n个子串，问长度为L的串有多少个，且这个串必须包含至少k个子串。

首先很明显我们定义的状态应该能说明的问题是，使用的长度，已经包含了那些串。

这个题目的困难之处就是使用了那些串的表示方式，其实还是很容易想到的，那就是位压缩。也就是说这个题可以理解为自动机与位dp的结合。

这是状态也就很清晰了，dp[i][j][k]表示长度为i时，走到j节点包含的串为k（位压缩标记）的方法总数。

这里有两个优化，

一是比较显而易见的就是如果dp[i][j][k] 这个状态不存在，我们就没有必要利用它去推导i+1的状态。

二是因为i只与i-1有关系，所以可以用滚动数组，只是这个状态转移需要累加，所以每次要将上一维清零。

code：

/*
    hdu2825
*/

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

#define maxn 26
#define maxm 11
#define maxml 11
#define maxstate 100
#define maxdate 4097
#define size 26
#define mod 20090717
int dp[2][maxstate][maxdate];

struct automatonNode{
    automatonNode* next[size], * fail;
    int real, id;
    void clear(){
        real = id = 0;
        memset(next, NULL, sizeof(next));
    }
};

struct automaton{
    automatonNode* root, * link, ** queue;
    int ad;
    automaton(){
        link = new automatonNode[maxstate];
        queue = new automatonNode* [maxstate];
    }
    ~automaton(){
        delete[] link;
        delete[] queue;
    }
    /* 初始化自动机 */
    void clear(){
        ad = 0;
        root = &link[ad ++];
        root->clear();
        root->fail = root;
    }
    /* 字符转换 */
    int cg(char ch){
        return ch - 'a';
    }
    /* 插入字符串到自动机 */
    void insert(char *str, int pid){
        automatonNode* rt = root;
        for(int i = 0; str[i] != NULL; ++ i){
            if(rt->next[cg(str[i])] == NULL){
                rt->next[cg(str[i])] = &link[ad ++];
                rt->next[cg(str[i])]->clear();
                rt->next[cg(str[i])]->id = ad - 1;
            }
            rt = rt->next[cg(str[i])];
        }
        rt->real |= 1 << pid;
    }
    /* 建立自动机虚拟边及后缀指针 */
    void built(){
        int head = 0, tail = 0;
        automatonNode* fa;
        queue[tail ++] = root;
        while(head != tail){
            fa = queue[head ++];
            for(int i = 0; i < size; ++ i){
                if(fa->next[i] == NULL){
                    fa->next[i] = (fa == root) ? (fa) : (fa->fail->next[i]);
                }
                else{
                    fa->next[i]->fail = (fa == root) ? (fa) : (fa->fail->next[i]);
                    fa->next[i]->real |= fa->next[i]->fail->real;
                    queue[tail ++] = fa->next[i];
                }
            }
        }
    }
    /* 自动机Dp */
    void automatondp(int n, int m, int least){
        int state = 1 << (m + 1), k0(0), k1(1); 
        memset(dp, 0, sizeof(dp));
        dp[0][0][0] = 1;
        for(int i = 0; i < n; ++ i){
            for(int j = 0; j < ad; ++ j){
                for(int k = 0; k <= state; ++ k){
                    if(!dp[k0][j][k]) continue;
                    for(int t = 0; t < size; ++ t){
                        automatonNode* rt = &link[j], * temp = rt->next[t];
                        int son = temp->id;
                        dp[k1][son][k | temp->real] = (dp[k1][son][k | temp->real] + dp[k0][j][k]) % mod;
                    }
                }
            }
            k0 ^= 1;
            k1 ^= 1;
            memset(dp[k1], 0, sizeof(dp[k1]));
        }
        int ans = 0, temp, x;
        for(int j = 0; j < ad; ++ j){
            for(int k = 0; k <= state; ++ k){
                if(dp[k0][j][k]){
                    temp = 0, x = k;
                    while(x){
                        if(x & 1) temp ++;
                        x >>= 1;
                    }
                    if(temp >= least) ans = (ans + dp[k0][j][k]) % mod;
                }
            }
        }
        printf("%d\n", ans);
    }
};


int main(){
    int n, m, k;
    char str[maxml];
    automaton aut;
    while(~scanf("%d%d%d", &n, &m, &k), n || m || k){
        aut.clear();
        for(int i = 0; i < m; ++ i){
            scanf("%s", str);
            aut.insert(str, i + 1);
        }
        aut.built();
        aut.automatondp(n, m, k);
    }
    return 0;
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

第二题：

http://acm.hdu.edu.cn/showproblem.php?pid=2296

ring

好题，调了1天多才调出来。题目是说给出n个子串，每个子串都有一个不同的权值，让你构造一个长度不超过L的串，他包含的子串的总权值最大，同一个串出现多次算多次的权值。

因为不用判重，所以也就不用记录包含了那些串，只需要记录得到的权值和使用的长度就可以了。因此状态是dp[i][j]表示使用长度是i，走到j节点能得到的最大权值。只是这个题还有个要求就是在权值最大的前提下，输出长度尽量短，字典序尽量小的那个。

这时我们加个数组path记录一下得到dp[i][j]时能得到的字典序小的一个串是什么。

code：

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

#define maxn 55
#define maxm 101
#define maxml 12
#define maxstate 1200
#define size 26

int dp[maxn][maxstate];
char path[maxn][maxstate][maxn], copp[maxn];
int val[maxm];

struct automatonNode{
    automatonNode* next[size], * fail;
    int real, id;
    char ch;
    void clear(){
        real = id = 0;
        memset(next, NULL, sizeof(next));
    }
};

struct automaton{
    automatonNode* root, * link, ** queue;
    int ad;
    automaton(){
        link = new automatonNode[maxstate];
        queue = new automatonNode* [maxstate];
    }
    ~automaton(){
        delete[] link;
        delete[] queue;
    }
    /* 初始化自动机 */
    void clear(){
        ad = 0;
        root = &link[ad ++];
        root->clear();
    }
    /* 字符转换 */
    int cg(char ch){
        return ch - 'a';
    }
    /* 插入字符串到自动机 */
    void insert(char *str, int pid){
        automatonNode* rt = root;
        for(int i = 0; str[i] != '\0'; ++ i){
            if(rt->next[cg(str[i])] == NULL){
                rt->next[cg(str[i])] = &link[ad ++];
                rt->next[cg(str[i])]->clear();
                rt->next[cg(str[i])]->id = ad - 1;
                rt->next[cg(str[i])]->ch = str[i];
            }
            rt = rt->next[cg(str[i])];
        }
        rt->real = pid;
    }
    /* 建立自动机虚拟边及后缀指针 */
    void built(){
        int head = 0, tail = 0;
        automatonNode* fa;
        queue[tail ++] = root;
        while(head != tail){
            fa = queue[head ++];
            for(int i = 0; i < size; ++ i){
                if(fa->next[i] == NULL){
                    fa->next[i] = (fa == root) ? (fa) : (fa->fail->next[i]);
                }
                else{
                    fa->next[i]->fail = (fa == root) ? (fa) : (fa->fail->next[i]);
                    fa->next[i]->real = val[fa->next[i]->real];
                    fa->next[i]->real += fa->next[i]->fail->real;
                    queue[tail ++] = fa->next[i];
                }
            }
        }
    }
    bool comp(int i, int j, int id, int t){
        strcpy(copp, path[i][j]);
        copp[i] = t + 'a';
        copp[i + 1] = '\0';
        return strcmp(path[i + 1][id], copp) > 0;
    }
    /* 自动机dp */
    void automatondp(int n, int m){
        memset(dp, -1, sizeof(dp));
        memset(path, 0, sizeof(path));
        dp[0][0] = 0;
        copp[0] = '\0';
        for(int i = 0 ; i < n; ++ i){
            for(int j = 0; j < ad; ++ j){
                if(dp[i][j] < 0) continue;
                for(int t = 0; t < size; ++ t){
                    automatonNode *temp = link[j].next[t];
                    int id = temp->id;
                    if((dp[i + 1][id] < dp[i][j] + temp->real) || (dp[i + 1][id] == dp[i][j] + temp->real && comp(i, j, id, t))){
                        dp[i + 1][id] = dp[i][j] + temp->real;
                        strcpy(path[i + 1][id], path[i][j]);
                        path[i + 1][id][i] = t + 'a';
                        path[i + 1][id][i + 1] = '\0';
                    }
                }
            }
        }
        int max = 0, maxl = 0;
        copp[0] = '\0';
        for(int i = 0; i <= n; ++ i){
            for(int j = 0; j < ad; ++ j){
                if(dp[i][j] > max || (dp[i][j] == max && i == maxl && strcmp(copp, path[i][j]) > 0 )){
                    max = dp[i][j];
                    maxl = i;
                    strcpy(copp, path[i][j]);
                }
            }
        }
        printf("%s\n", copp);
    }
};

int main(){
    int n, m, CASE;
    automaton aut;
    char str[maxml];
    scanf("%d", &CASE);
    while(CASE --){
        scanf("%d %d", &n, &m);
        aut.clear();
        for(int i = 0; i < m; ++ i){
            scanf("%s", str);
            aut.insert(str, i + 1);
        }
        for(int i = 1; i <= m; ++ i){
            scanf("%d", &val[i]);
        }
        aut.built();
        aut.automatondp(n, m);
    }
    return 0;
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

第三题：

http://acm.hdu.edu.cn/showproblem.php?pid=2457

http://poj.org/problem?id=3691

DNA repair

给出n个子串，再给出一个文本串，问至少修改几次，能让文本串不包含任何一个子串，串的字符集是AGTC，修改的方式只能是将一个字符变为另一个字符，而且都是AGTC里的。

Dp[i][j]表示串的前i个，到达状态j需要修改的最少次数，转移的时候看看你走的边和第i+1个字符是否一样，一样就说明不用修改，不一样就说明要修改，切忌危险节点不能走到，也不能去推导别的节点。

if(dp[i + 1][id]> dp[i][j] + (cg(str[i]) != t)) dp[i + 1][id] = dp[i][j] + (cg(str[i]) !=t);

这是转移方程。

code：

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

#define maxn 1010
#define maxm 51
#define maxml 21
#define maxstate 1000
#define size 4
#define inf 210000000
int dp[maxn][maxstate];

struct automatonNode{
    automatonNode* next[size], * fail;
    int id;
    bool real; 
    void clear(){
        memset(next, NULL, sizeof(next));
        real = id = 0;
    }
};

struct automaton{
    automatonNode* root, *link, ** queue;
    int ad;
    automaton(){
        link = new automatonNode[maxstate];
        queue = new automatonNode* [maxstate];
    }
    ~automaton(){
        delete[] link;
        delete[] queue;
    }
    /* 初始化 */
    void clear(){
        ad = 0;
        root = &link[ad ++];
        root->clear();
        root->fail = root;
    }
    /* 字符向size映射 */
    int cg(char ch){
        if(ch == 'A') return 0;
        if(ch == 'C') return 1;
        if(ch == 'G') return 2;
        if(ch == 'T') return 3;
    }
    /* 插入字符串 */
    void insert(char * st){
        automatonNode* rt = root;
        for(int i = 0; st[i] != '\0'; ++ i){
            if(rt->next[cg(st[i])] == NULL){
                rt->next[cg(st[i])] = &link[ad ++];
                rt->next[cg(st[i])]->clear();
                rt->next[cg(st[i])]->id = ad - 1;
            }
            rt = rt->next[cg(st[i])];
        }
        rt->real = 1;
    }
    /* 建立自动机 */
    void built(){
        int head = 0, tail = 0;
        automatonNode * fa;
        queue[tail ++] = root;
        while(head != tail){
            fa = queue[head ++];
            for(int i = 0; i < size; ++ i){
                if(fa->next[i] == NULL){
                    fa->next[i] = (fa == root) ? (fa) : (fa->fail->next[i]);
                }
                else{
                    fa->next[i]->fail = (fa == root) ? (fa) : (fa->fail->next[i]);
                    fa->next[i]->real |= (fa->next[i]->fail->real | fa->real);
                    queue[tail ++] = fa->next[i];
                }
            }
        }
    }
    /* 自动机Dp */
    void automatonDp(char* str, int n, int m){
        for(int i = 0; i <= n; ++ i){
            for(int j = 0; j < ad; ++ j) dp[i][j] = inf;
        }
        dp[0][0] = 0;
        for(int i = 0; i < n; ++ i){
            for(int j = 0; j < ad; ++ j){
                if(dp[i][j] >= inf || link[j].real) continue;
                for(int t = 0; t < size; ++ t){
                    automatonNode* rt = link[j].next[t];
                    int id = rt->id;
                    if(rt->real) continue;
                    if(dp[i + 1][id] > dp[i][j] + (cg(str[i]) != t)) dp[i + 1][id] = dp[i][j] + (cg(str[i]) != t);
                }
            }
        }
        int min = inf;
        for(int j = 0; j < ad; ++ j){
            if(dp[n][j] < min) min = dp[n][j];
        }
        printf("%d\n", min >= inf ? -1 : min);
    }
};

int main(){
    int n, m, CASE = 0;
    char str[maxn];
    automaton aut;
    while(~scanf("%d", &m), m){
        aut.clear();
        for(int i = 0; i < m; ++ i){
            scanf("%s", str);
            aut.insert(str);
        }
        aut.built();
        scanf("%s", str);
        n = strlen(str);
        printf("Case %d: ", ++CASE);
        aut.automatonDp(str, n, m);
    }
    return 0;
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

第四题：

http://acm.hdu.edu.cn/showproblem.php?pid=3341

Lost's revenge

给出n个子串，给处一个文本串，问将文本串重新排列后，能包含的最多的子串的个数是多少，子串可重叠。字符只包含AGTC，首先可乱序重排就说明题目告诉我们的是每个字符可使用的个数。然后求利用这些字符组合出来的串最多能包含多少个子串。

因此dp方程似乎就出来了 dp[A][G][T][C][j]使用了A个A，G个G。。。。走到状态j能包含的最多子串，但是由于A，G,T，C的个数是40，因此这个状态太大了，怎么办？放弃？

不，想想变进制吧，想想在排列的hash中变进制的使用。这里相当于是4个位ACGT

每个位上的最大值就是他们的个数。加上A有3个，C有4个，G有2个，T有5个，那么这说明第0位是逢5进一，第1位是逢2进一。。。。。这样每一位上能表示的最大值就能算出来了。

设有na个A、nc个C、ng个G、nt个T

s表示由ma个A、mc个C、mg个G、mt个T的生成串

s可表示为ma*(nc+1)*(ng+1)*(nt+1)+mc*(ng+1)*(nt+1)+mg*(nt+1)+mt

每个值都小于40 而且na+nb+nc+nt <=40，应此s是一个最高项为4次方的函数

这些，所以na，nb，nc，nd都是10时，s最大，这个可以想象一下，当x+y=20时，z=xy最大值时x和y的取值。

为了推导方便，我们将状态定义为：dp[a][c][g][t][j]剩余a个A，c个C，g个G。。。时，走到状态j的最多包含的子串数，然后用变进制转化这个状态。

code：

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

#define maxn 51
#define maxnl 11
#define maxm 41
#define maxstate 510
#define maxnum 15000
#define size 4

int dp[maxstate][maxnum];

struct automatonNode{
    automatonNode * next[size], * fail;
    bool trues[size];
    int real, id;
    void clear(){
        memset(next, NULL, sizeof(next));
        memset(trues, 0, sizeof(trues));
        real = id = 0;
    }
};

struct automaton{
    automatonNode * root, * link, ** queue;
    int ad;
    automaton(){
        link = new automatonNode[maxstate];
        queue = new automatonNode * [maxstate];
    }
    ~automaton(){
        delete[] link;
        delete[] queue;
    }
    /* 初始化自动机 */
    void clear(){
        ad = 0;
        root = &link[ad++];
        root->clear();
        root->fail = root;
    }
    /* 字符到size的映射 */
    int cg(char ch){
        if(ch == 'A') return 0;
        if(ch == 'C') return 1;
        if(ch == 'G') return 2;
        if(ch == 'T') return 3;
    }
    /* 插入字符串 */
    void insert(char * st){
        automatonNode* rt = root;
        for(int i = 0; st[i] != '\0'; ++ i){
            if(rt->next[cg(st[i])] == NULL){
                rt->next[cg(st[i])] = &link[ad ++];
                rt->next[cg(st[i])]->clear();
                rt->trues[cg(st[i])] = 1;
                rt->next[cg(st[i])]->id = ad - 1;
            }
            rt = rt->next[cg(st[i])];
        }
        rt->real ++;
    }
    /* 建立自动机 */
    void built(){
        int head = 0, tail = 0;
        automatonNode * fa;
        queue[tail ++] = root;
        while(head != tail){
            fa = queue[head ++];
            for(int i = 0; i < size; ++ i){
                if(fa->next[i] == NULL){
                    fa->next[i] = (fa == root) ? (fa) : (fa->fail->next[i]);
                }
                else{
                    fa->next[i]->fail = (fa == root) ? (fa) : (fa->fail->next[i]);
                    fa->next[i]->real += fa->next[i]->fail->real;
                    queue[tail ++] = fa->next[i];
                }
            }
        }
    }
    /* 自动机Dp */
    void automatonDp(int n, char * str){
        int num[size], used[size], carr[size + 1], sum = 1;
        memset(num, 0, sizeof(num));
        for(int i = 0; str[i] != '\0'; ++ i){
            num[cg(str[i])] ++;
        }
        for(int i = 0; i < size + 1; ++ i){
            carr[i] = sum;
            sum *= (num[i] + 1);
        }
        memset(dp, -1, sizeof(dp));
        dp[0][carr[size] - 1] = 0;
        for(used[3] = num[3]; used[3] >= 0; -- used[3]){
            for(used[2] = num[2]; used[2] >= 0; -- used[2]){
                for(used[1] = num[1]; used[1] >= 0; -- used[1]){
                    for(used[0] = num[0]; used[0] >= 0; -- used[0]){
                        int state = 0;
                        for(int t = 0; t < size; ++ t) state += used[t] * carr[t];
                        for(int j = 0; j < ad; ++ j){
                            if(dp[j][state] < 0) continue;
                            for(int t = 0; t < size; ++ t){
                                automatonNode* rt = link[j].next[t];
                                int id = rt->id;
                                if(used[t] && dp[j][state] + rt->real > dp[id][state - carr[t]]){
                                    dp[id][state - carr[t]] = dp[j][state] + rt->real;
                                }
                            }
                        }
                    }
                }
            }
        }
        int max = 0;
        for(int j = 0; j < ad; ++ j){
            if(max < dp[j][0]) max = dp[j][0];
        }
        printf("%d\n", max);
    }
};

int main(){
    int n, CASE = 0;
    char str[maxm];
    automaton aut;
    while(~scanf("%d", &n), n){
        aut.clear();
        for(int i = 0; i < n; ++ i){
            scanf("%s", str);
            aut.insert(str);
        }
        aut.built();
        scanf("%s", str);
        printf("Case %d: ", ++CASE);
        aut.automatonDp(n, str);
    }
    return 0;
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

第五题：

http://acm.hdu.edu.cn/showproblem.php?pid=3247

Resource Archiver

给出n个01安全串和m个01危险串，求包含所有安全串且不包含所有危险串的最短长度，思路就是求出任意两个串的链接在一起的最短长度，然后就成了将所有串连在一起的最短长度，这个就可以使用状态压缩Dp来计算。

详细请见

http://blog.csdn.net/threedonkey/article/details/7394819

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

第六题

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3545

Rescue the Rabbit

2012来了。。。为了挽救兔子这一物种，生物学家研究了一些DNA序列，对于每种序列有一个权值，可正可负，现在让你构造一个DNA序列，使得权值最大（不可重复统计）。如果不存在，输出2012后没有兔子了。

这个是包含的字符串权值只能被算一次，而且有正有负，还是状态压缩Dp；

dp[i][j][k]表示长度为i走到节点j包含串为k的最大权值。

code：

#include <cstdio>
#include <cstring>

#define SIZE 4
#define MAXN 11
#define MAXM 110
#define MAXL 21
#define STATE 1024

struct _Trie{
    int next[SIZE];
    int id;
    int suffix;
};

_Trie trie[MAXN * MAXL];
bool dp[MAXM][MAXN * MAXL][STATE];
int state, MAXSTATE;
int weight[MAXN];

void clear(){
    state = 1;
    for(int i = 0; i < SIZE; ++ i) trie[0].next[i] = -1;
    trie[0].id = 0;
}

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

void insert(char *s, int id){
    int rt = 0;
    for(; *s != '\0'; ++ s){
        if(trie[rt].next[cg(*s)] == -1){
            trie[rt].next[cg(*s)] = state;
            trie[state].id = 0;
            trie[state].suffix = 0;
            for(int j = 0; j < SIZE; ++ j) trie[state].next[j] = -1;
            rt = state ++;
        }
        else rt = trie[rt].next[cg(*s)];
    }
    trie[rt].id = 1 << id;
}

void input(int n){
    int i;
    char str[MAXL];
    clear();
    for(i = 0; i < n; ++ i){
        scanf("%s %d", str, &weight[i]);
        insert(str, i);
    }
}

void Built_trie_map(){
    int queue[MAXN * MAXL];
    int opt, head, tail, g, i;
    head = tail = 0;
    trie[0].suffix = 0;
    queue[tail ++] = 0;
    while(head < tail){
        opt = queue[head ++];
        for(i = 0; i < SIZE; ++ i){
            g = trie[opt].next[i];
            if(g == -1) trie[opt].next[i] = trie[trie[opt].suffix].next[i] * (opt != 0);
            else{
                trie[g].suffix = trie[trie[opt].suffix].next[i] * (opt != 0);
                trie[g].id |= trie[trie[g].suffix].id;
                queue[tail ++] = g;
            }
        }
    }
}

void get_dp(int m, int n){
    int i, j, k, p;
    MAXSTATE = 1 << n;
    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1;
    for(i = 0; i < m; ++ i){
        for(j = 0; j < state; ++ j){
            for(p = 0; p < MAXSTATE; ++ p){
                if(dp[i][j][p]){
                    for(k = 0; k < SIZE; ++ k){
                        int v = trie[j].next[k];
                        dp[i + 1][v][p | trie[v].id] = 1;
                    }
                }
            }
        }
    }
}

void get_ans(int m, int n){
    int i, j, ans = -11111111, max = 0;
    for(i = 0; i < state; ++ i){
        for(j = 0; j < MAXSTATE; ++ j){
            if(dp[m][i][j]){
                max = 0;
                for(int k = 0; k < n; ++ k){
                    max += ((j & (1 << k)) > 0) * weight[k];
                }
                if(max > ans) ans = max;
            }
        }
    }
    if(ans >= 0) printf("%d\n", ans);
    else printf("No Rabbit after 2012!\n");
}

int main(){
    int n, m;
    while(~scanf("%d %d", &n, &m)){
        input(n);
        Built_trie_map();
        get_dp(m, n);
        get_ans(m, n);
    }
    return 0;
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

第七题

http://acm.hdu.edu.cn/showproblem.php?pid=3689

Infinite monkeytheorem

给出打出每个字符的概率，和打击次数，询问打出给定的串的概率。

把给定的那个串放入自动机中，然后dp[i][j]表示答应i次走到节点j的概率。

最后的dp【0..L】[ad – 1 ] 便是答案。

code：

#include <stdio.h>
#include <string.h>
#define MAXN (26)
#define MAXM (1010)
#define MAXL (20)

struct NODE{
    int next[MAXN];
    int falg;
    int suffix;
    int father;
}trie[MAXL * MAXN];
int ad;
char word[MAXL];
double prob[MAXN];
double f[MAXM][MAXL];
int queue[MAXL * MAXN], boo[MAXL * MAXN];

void insert(){
    int q = 0;
    for(int i = 0; word[i] != '\0'; i ++){
        if(trie[q].next[word[i] - 'a'] == -1){
            trie[q].next[word[i] - 'a'] = ad;
            trie[ad ++].father = q;
        }
        q = trie[q].next[word[i] - 'a'];
    }
    trie[q].falg = 1;
}

void Get_trie_map(){
    int head, tail, i, opt, g, j;
    memset(boo, 0, sizeof(boo));
    head = tail = 0;
    trie[0].suffix = 0;
    boo[0] = 1;
    for(i = 0; i < MAXN; i ++)
        if(trie[0].next[i] == -1) trie[0].next[i] = 0;
        else trie[trie[0].next[i]].suffix = 0;
    queue[tail ++] = 0;
    while(head < tail){
        opt = queue[head ++];
        for(i = 0; i < MAXN; i ++)
            if(trie[opt].next[i] > opt && !boo[trie[opt].next[i]]){
                queue[tail ++] = g = trie[opt].next[i];
                boo[g] = 1;
                if(trie[g].suffix == -1) trie[g].suffix = trie[trie[opt].suffix].next[i];
                for(j = 0; j < MAXN; j ++)
                    if(trie[g].next[j] == -1) trie[g].next[j] = trie[trie[g].suffix].next[j];
            }
    }
}


void Built_trie(){
    scanf("%s", word);
    ad = 1;
    memset(trie, -1, sizeof(trie));
    insert();
    Get_trie_map();
}

double Get_ans(int m){
    int i, j, k;
    double ans = 0;
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for(i = 0; i < m; i ++)
        for(j = 0; j < ad - 1; j ++)
            if(i >= j)
                for(k = 0; k < MAXN; k ++){
                    int v = trie[j].next[k];
                    f[i + 1][v] += f[i][j] * prob[k];
                }
    for(i = 0; i <= m; i ++)
        ans += f[i][ad - 1];
    return ans;
}

                


int main(){
    int n, m, i;
    char ch[2];
    double pro, ans;
    while(~scanf("%d %d", &n, &m), n && m){
        memset(prob, 0, sizeof(prob));
        for(i = 0; i < n; i ++){
            scanf("%1s %lf", ch, &pro);
            prob[ch[0] - 'a'] = pro;
        }
        Built_trie();
        ans = Get_ans(m) * 100;
        printf("%.2lf%%\n", ans);

    }
    return 0;
}

code：

上一篇：coach purses 58307
下一篇：poj 3991(括号匹配)

AC自动机 初步总结

AC自动机总结

相关文章

AC自动机初步总结