当前位置:编程学习 > C/C++ >>

POJ 2778 AC自动机

这题还是挺经典的

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

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

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

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

 

 

[cpp]
include <iostream>  
#include <algorithm>  
#include <cstring>  
#include <string>  
#include <cstdio>  
#include <cmath>  
#include <queue>  
#include <map>  
#include <set>  
#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) 
            &

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,