最近研究data矩陣，稍微總結(jié)一下，以后繼續(xù)補充：

????ac自動機處理字符串，dp計算謎底，用矩陣來減速

每日一道理
巴爾扎克說過“不幸，是天才的進升階梯，信徒的洗禮之水，弱者的無底深淵”。風(fēng)雨過后，眼前會是鷗翔魚游的天水一色；走出荊棘，前面就是鋪滿鮮花的康莊大道；登上山頂，腳下便是積翠如云的空蒙山色。 在這個世界上，一星隕落，黯淡不了星空燦爛，一花凋零，荒蕪不了整個春天。人生要盡全力度過每一關(guān)，不管遇到什么困難不可輕言放棄。
#include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std; const long long mod=100000; struct {int next[30],tmp,fail,lon; }trie[111]; int lon; int m,n; struct matrix {long long data[111][111];int size;matrix(int tmp,int lon){size=lon;for(int i=0;i<=size;i++)for(int j=0;j<=size;j++)data[i][j]=tmp;}matrix operator * (const matrix &xx) const{matrix ans(0,size);for(int p=0;p<=size;p++)for(int q=0;q<=size;q++)for(int i=0;i<=size;i++){ans.data[p][q]+=data[p][i]*xx.data[i][q];ans.data[p][q]%=mod;}return(ans);} }; void trieini() {memset(trie,0,sizeof(trie));lon=0; } void insert(char s[]) {int t=0;int n=strlen(s+1);for(int i=1;i<=n;i++){if(trie[t].next[s[i]-'A']==0){trie[t].next[s[i]-'A']=++lon;trie[lon].lon=i;}t=trie[t].next[s[i]-'A'];if(i==n)trie[t].tmp++;} }void getfail() {int root=0;queue <int> q;q.push(root);trie[root].fail=root;while(!q.empty()){int t=q.front();q.pop();for(int i=0;i<26;i++){if(trie[t].next[i]){if(t==root){int u=trie[t].next[i];trie[u].fail=root;q.push(u);continue;}int u=trie[t].next[i];int tmp=trie[t].fail;while(tmp!=root&&trie[tmp].next[i]==0)tmp=trie[tmp].fail;if(trie[tmp].next[i])trie[u].fail=trie[tmp].next[i];elsetrie[u].fail=root;q.push(u);}}}for(int i=1;i<=lon;i++){int t=i;while(t!=root){int u=trie[t].fail;trie[t].tmp+=trie[u].tmp;t=u;}} }void find(matrix &a) {int root=0;for(int k=0;k<=lon;k++){if(trie[k].tmp) continue;for(int i=0;i<26;i++){if(i+'A'!='A')if(i+'A'!='C')if(i+'A'!='T')if(i+'A'!='G')continue;int t=k;while(t!=root&&trie[t].next[i]==0)t=trie[t].fail;if(trie[t].next[i]){int u=trie[t].next[i];if(!trie[u].tmp)a.data[k][u]++;}elsea.data[k][0]++;}} }int main() {while(scanf("%d %d",&m,&n)!=EOF){trieini();char s[15];for(int i=1;i<=m;i++){scanf("%s",s+1);insert(s);}getfail();matrix a(0,lon);find(a);matrix ans(a);n--;while(n){if(n&1)ans=ans*a;a=a*a;n/=2;}int answer=0;for(int i=0;i<=lon;i++){answer+=ans.data[0][i];answer%=mod;}cout<<answer<<endl;}return 0; }

文章結(jié)束給大家分享下程序員的一些笑話語錄： IBM和波音777
　　波音777是有史以來第一架完全在電腦虛擬現(xiàn)實中設(shè)計制造的飛機，所用的設(shè)備完全由IBM公司所提供。試飛前，波音公司的總裁非常熱情的邀請IBM的技術(shù)主管去參加試飛，可那位主管卻說道:“啊，非常榮幸，可惜那天是我妻子的生日，So..”..
　　波音公司的總載一聽就生氣了:“膽小鬼，我還沒告訴你試飛的日期呢!”

--------------------------------- 原創(chuàng)文章 By
data和矩陣
---------------------------------

轉(zhuǎn)載于:https://www.cnblogs.com/jiangu66/p/3153247.html

總結(jié)

以上是生活随笔為你收集整理的data矩阵poj 2778 DNA Sequence的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。