POJ 2778 DNA Sequence AC自动机矩阵快速幂

2019-11-08 01:19:58

字体：大中小

来源：转载

供稿：网友

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

利用AC自动机构建好trie图确定可以转移的状态构造trie图的邻接矩阵矩阵第i行j列表示从i出发到j可行的路径数矩阵的k次方就相当于走k步(构造一个长度为k的串)的可行方案数答案即为 a[root][1] + a[root][2] … + a[root][cnt] (%%%szb)

#include <cstdio>#include <algorithm>#include <cstring>#include <queue>#include <cmath>#define MAXN 15*15using namespace std;const int MOD = 100000;int n,m,ans=0;char a[15];struct mat{ int siz; long long a[105][105]; mat(int t) { siz=t; memset(a,0,sizeof a); } mat Operator *(const mat &t) const { mat ans=mat(siz); for(int i=1;i<=siz;i++) for(int j=1;j<=siz;j++) for(int k=1;k<=siz;k++) ans.a[i][j]=(ans.a[i][j]+a[i][k]*t.a[k][j])%MOD; return ans; } void init() { for(int i=1;i<=siz;i++) a[i][i]=1; }};struct AC{ int root,cnt; int nx[MAXN][4],fail[MAXN]; bool end[MAXN]; int f(char s) { if(s=='A') return 0; if(s=='T') return 1; if(s=='G') return 2; if(s=='C') return 3; } int newnode() { cnt++; for(int i=0;i<4;i++) nx[cnt][i]=0; end[cnt]=fail[cnt]=0; return cnt; } void init() { cnt=0; root=newnode(); } void insert(char *s) { int len=strlen(s),now=root; for(int i=0;i<len;i++) { if(!nx[now][f(s[i])]) nx[now][f(s[i])]=newnode(); now=nx[now][f(s[i])]; } end[now]=1; } void build_fail() { queue<int> q; for(int i=0;i<4;i++) { if(!nx[root][i]) nx[root][i]=root; else fail[nx[root][i]]=root,q.push(nx[root][i]); } while(!q.empty()) { int now=q.front(); if(end[fail[now]]) end[now]=1; for(int i=0;i<4;i++) { if(nx[now][i]) { fail[nx[now][i]]=nx[fail[now]][i]; q.push(nx[now][i]); } else nx[now][i]=nx[fail[now]][i]; } q.pop(); } } mat get_mat() { mat t=mat(cnt); for(int i=1;i<=cnt;i++) { if(end[i]) continue; for(int j=0;j<4;j++) if(!end[nx[i][j]]) t.a[i][nx[i][j]]++; } return t; }}AC;mat fpow(mat x,int k){ mat ans(x.siz); ans.init(); while(k) { if(k&1) ans=ans*x; k>>=1; x=x*x; } return ans;}int main(){ while(scanf("%d%d",&n,&m)!=EOF) { AC.init(); for(int i=1;i<=n;i++) { scanf("%s",a); AC.insert(a); } AC.build_fail(); mat t=fpow(AC.get_mat(),m); for(int i=1;i<=AC.cnt;i++) ans=(ans+t.a[1][i])%MOD; PRintf("%d/n",ans); } return 0;}

上一篇：通过ajax请求springmvc，将值显示在select下拉框中

下一篇：（区别）递归与迭代&&递归与递推&&迭代与递推