本文主要是介绍poj 2778 AC自动机 + 矩阵快速幂，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
// poj 2778 AC自动机 + 矩阵快速幂
//
// 题目链接：
//
// http://poj.org/problem?id=2778
//
// 解题思路：
//
// 建立AC自动机,确定状态之间的关系,构造出,走一步
// 能到达的状态矩阵,然后进行n次乘法,就可以得到状态间
// 走n步的方法数.
// 精髓:
// 1):这个ac自动机有一些特别,根节点是为空串,然而
// 每走一步的时候,如果没法走了,这时候,不一定是回到根
// 节点,因为有可能单个的字符时病毒,这样,不是随便就能达到
// 所谓的根节点的,所以每次初始化的时候,不能是0,而应该是
// -1.
//
// 感悟:
//
// 这道AC自动机,开始我是完全不会,知道是AC自动机+矩阵快速幂
// 开始,自以为AC自动机构造的很对,而且样例都过了好嘛,结果一直是
// wrong answer.我就不信邪了,肯定是博主博客有错误,我就将博主的
// 交了一发,然而,博主的过了,我的没过.哎,一阵伤心,但心里也是再次
// 燃起了希望之火,还是可以搞得.然而我就仔细研究,对拍呗,自己造了
// 几个样例.发现下面这组:
// 4 2
// A
// C
// T
// GT
// 这组样例,答案应该是1,而我的答案是3.我仿佛一下子恍然大悟,发现
// 单个字符是病毒,不能走回根节点.明白了过后,一改,就AC了,虽然速度
// 有点慢,但是我发现自己对AC自动机的理解又有了一点小小的新的拓展
// 虽然作为菜鸟的我敢于怀疑是一件好事,但是自己的不对就是不对,不要
// 因为自己的自信就去刻意寻找别人的错误,认为别人是错误的.有着一颗
// 敢于承认错误,并且接受正确观念,并明悟的人,我觉得光明,就在前方!#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;typedef long long ll;const int MAX_NODE = 110;
const ll MOD = 100000;
const int MAX_N = 110;struct Matrix{ll mat[MAX_N][MAX_N];
}res;int n,m;struct Aho_Corasick{int ch[MAX_NODE][4];bool val[MAX_NODE];int f[MAX_NODE];//int last[MAX_NODE];int sz;void init(){memset(ch[0],-1,sizeof(ch[0]));val[0] = 0;sz = 1;f[0] = 0;//last[0] = 0;}int idx(char c){if (c == 'A')return 0;if (c == 'T')return 1;if (c == 'C')return 2;return 3;}void insert(char *s){int u = 0;int n = strlen(s);for (int i=0;i<n;i++){int c = idx(s[i]);if (ch[u][c]==-1){memset(ch[sz],-1,sizeof(ch[sz]));val[sz] = 0;ch[u][c] = sz++;}u = ch[u][c];}val[u] = true;}void getfail(){queue<int> que;f[0] = 0;for (int c = 0;c < 4;c++){int u = ch[0][c];if (u!=-1){que.push(u);f[u] = 0;// last[u] = 0;}else{ch[0][c] = 0; //表示当此c单个字符不是病毒的时候,则可以走回根}}while(!que.empty()){int r = que.front();que.pop();if (val[f[r]]) // 当r的某个后缀为病毒的时候标记此rval[r] = true;for (int c = 0; c < 4;c++){int u = ch[r][c];if (u == -1){ch[r][c] = ch[f[r]][c]; //把不存在的边接上去continue;}que.push(u);int v = f[r];while(v && ch[v][c]==-1)v = f[v];f[u] = ch[v][c];//last[u] = val[f[u]] ? f[u] : last[f[u]];}}}void get_matrix(){memset(res.mat,0,sizeof(res.mat));for (int u=0;u<sz;u++){for (int c = 0;c < 4;c++){if (!val[u] && !val[ch[u][c]])res.mat[u][ch[u][c]]++;}}}}ac;Matrix Mulity(Matrix a,Matrix b){Matrix ans;for (int i=0;i < ac.sz;i++)for (int j=0;j < ac.sz;j++){ans.mat[i][j] = 0;for (int k=0;k < ac.sz ;k++)ans.mat[i][j] = (ans.mat[i][j] + a.mat[i][k] * b.mat[k][j])%MOD;ans.mat[i][j] %= MOD;}return ans;
}Matrix Matrix_power(Matrix a,int b){Matrix ans;memset(ans.mat,0,sizeof(ans.mat));for (int i=0;i<ac.sz;i++)ans.mat[i][i] = 1;while(b){if (b & 1) ans = Mulity(ans,a);a = Mulity(a,a);b >>=1;}return ans;
}void print(Matrix r){for (int i=0;i<ac.sz;i++){for (int j=0;j<ac.sz;j++)cout << r.mat[i][j] << " ";cout << endl;}
}void input(){ac.init();char s[20];for (int i=1;i<=m;i++){scanf("%s",s);ac.insert(s);}ac.getfail();ac.get_matrix();
// print(res);res = Matrix_power(res,n);
// cout << endl;
// print(res);ll ans = 0;for (int i=0;i<ac.sz;i++){ans = (ans + res.mat[0][i])%MOD;}cout << ans%MOD << endl;
}int main(){//freopen("1.txt","r",stdin);while(scanf("%d%d",&m,&n)!=EOF){// puts("-------");input();}return 0;
}
这篇关于poj 2778 AC自动机 + 矩阵快速幂的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
