題目鏈接：點擊查看

題目大意：給出 n 個長度不大于 10 的字符串表示病毒串，再給出一個長度 len ，問長度為 len 的字符串中，有多少個字符串不含有病毒串作為子串

題目分析：因為病毒串的長度和數量均不大于 10 ，所以我們對病毒串構造AC自動機后會有最多 100 個結點代表 100 個狀態，注意對病毒串的標記，在構造AC自動機時記得把標記下傳，因為某個節點如果是病毒串的話，那么含有該前綴的后綴一定也是不可行的，我們可以對于這 100 個狀態構造矩陣，表示每個狀態到另一個狀態可行的方案數，最后利用快速冪求解就行了，對于這類題目而言還有一個地方不太明白，但網上的博客也都沒說明白，先當結論記著吧，就是為什么構造出的矩陣自乘 n 次后就是長度為 n 的字符串的可行方案數，也怪我自己上個學期的線性代數沒有學好，矩陣乘法或許有特殊的意義吧

對于這個題目而言還有一個細節，如果直接按照普通的矩陣快速冪模板寫的話會超時，因為每次都需要取模，也是這個題我才知道取模原來還是有時間代價的，我們可以減少取模次數以達到加速的效果

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=110;const int mod=100000; char s[N];int fail[N],trie[N][4],id[150],cnt;bool vis[N];struct Ma {LL a[N][N];Ma(){memset(a,0,sizeof(a));}Ma operator*(const Ma& b)const{Ma ans;for(int i=0;i<=cnt;i++)for(int j=0;j<=cnt;j++){for(int k=0;k<=cnt;k++)ans.a[i][j]+=a[i][k]*b.a[k][j];ans.a[i][j]%=mod;}return ans;} }maze;Ma q_pow(Ma a,LL b)//矩陣快速冪 {Ma ans;for(int i=0;i<=cnt;i++)ans.a[i][i]=1;while(b){if(b&1)ans=ans*a;a=a*a;b>>=1;}return ans; }void getmaze() {memset(maze.a,0,sizeof(maze.a));for(int i=0;i<=cnt;i++)if(!vis[i])for(int j=0;j<4;j++)if(!vis[trie[i][j]])maze.a[i][trie[i][j]]++; }void insert_word() {int len=strlen(s);int pos=0;for(int i=0;i<len;i++){int to=id[s[i]];if(!trie[pos][to])trie[pos][to]=++cnt;pos=trie[pos][to];}vis[pos]=true; }void getfail() {queue<int>q;for(int i=0;i<4;i++){if(trie[0][i]){fail[trie[0][i]]=0;q.push(trie[0][i]);}}while(!q.empty()){int cur=q.front();q.pop();if(vis[fail[cur]])vis[cur]=true;for(int i=0;i<4;i++){if(trie[cur][i]){fail[trie[cur][i]]=trie[fail[cur]][i];q.push(trie[cur][i]);}elsetrie[cur][i]=trie[fail[cur]][i];}} }void init() {cnt=0;memset(vis,false,sizeof(vis));memset(trie,0,sizeof(trie));id['A']=0,id['C']=1,id['G']=2,id['T']=3; }int main() { //#ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); //#endif // ios::sync_with_stdio(false);int n,m;while(scanf("%d%d",&n,&m)!=EOF){init();while(n--){scanf("%s",s);insert_word();}getfail();getmaze();maze=q_pow(maze,m);int ans=0;for(int i=0;i<=cnt;i++)ans=(ans+maze.a[0][i])%mod;printf("%d\n",ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的POJ - 2778 DNA Sequence(AC自动机+矩阵快速幂)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。