Codeforces 86C Genetic engineering (AC自动机+dp)
题目大意:
要求构造一个串,使得这个串是由所给的串相连接构成,连接可以有重叠的部分。
思路分析:
首先用所给的串建立自动机,每个单词节点记录当前节点能够达到的最长后缀。
开始的时候想的是dp[i][j]表示长度为i,走到自动机的j节点的答案。
但是显然既然是可以重复覆盖的,那么每一个节点的dp值都并不是最优的,因为可以从一个地方截断去连接另外一个串。
所以正确姿势就是dp [i] [j] [k] 表示构造到了长度为 i 的串, 现在这个串后面有k 个字符是没有找到有效的节点的,然后在自动机上走到了j。
那么转移的时候,就有两种情况。
isword >= k+1。。。为什么是k+1 因为我们现在是去找的儿子节点,已经加1了。这样的话就是这个节点可以完全覆盖没有匹配到的k个,换句话说就是让后面的k个字符找到了合法节点去匹配。那么就转移到dp [i+1] [j->next] [0]...
否则,如果k+1<=10 那么就让后面这个继续失配,那么久直接转移到 dp [i+1][j->next][k+1]...
最后累加答案。
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <utility> #include <string> #include <vector> #define inf 0x3f3f3f3f using namespace std; const int mod = 1000000009; const char tab = 'a'; const int max_next = 4; int rev[256]; struct trie { struct trie *fail; struct trie *next[max_next]; int isword; int index; }; struct AC { trie *que[100005],*root,ac[100005]; int head,tail; int idx; trie *New() { trie *temp=&ac[idx]; for(int i=0;i<max_next;i++)temp->next[i]=NULL; temp->fail=NULL; temp->isword=0; temp->index=idx++; return temp; } void init() { idx=0; root=New(); } void Insert(trie *root,char *word,int len){ trie *t=root; for(int i=0;i<len;i++){ if(t->next[rev[word[i]]]==NULL) t->next[rev[word[i]]]=New(); t=t->next[rev[word[i]]]; } t->isword=len; } void acbuild(trie *root){ int head=0,tail=0; que[tail++]=root; root->fail=NULL; while(head<tail){ trie *temp=que[head++],*p; for(int i=0;i<max_next;i++){ if(temp->next[i]){ if(temp==root)temp->next[i]->fail=root; else { p=temp->fail; while(p!=NULL){ if(p->next[i]){ temp->next[i]->fail=p->next[i]; break; } p=p->fail; } if(p==NULL)temp->next[i]->fail=root; } if(temp->next[i]->fail->isword) temp->next[i]->isword=max(temp->next[i]->isword,temp->next[i]->fail->isword); que[tail++]=temp->next[i]; } else if(temp==root)temp->next[i]=root; else temp->next[i]=temp->fail->next[i]; } } } void tra() { for(int i=0;i<idx;i++) { if(ac[i].fail!=NULL)printf("fail = %d ",ac[i].fail->index); for(int k=0;k<max_next;k++) printf("%d ",ac[i].next[k]->index); puts(""); } } }sa,sb; string cq[55]; char word[55]; int dp[1005][105][11]; void add(int &a,int b) { a+=b; if(a>=mod)a-=mod; } int solve(int L) { memset(dp,0,sizeof dp); dp[0][0][0]=1; for(int i=0;i<L;i++) { for(int j=0;j<sa.idx;j++) { for(int k=0;k<10;k++) { for(int d=0;d<4;d++) { if(sa.ac[j].next[d]->isword>=k+1) add(dp[i+1][sa.ac[j].next[d]->index][0],dp[i][j][k]); else if(k+1<=10) add(dp[i+1][sa.ac[j].next[d]->index][k+1],dp[i][j][k]); } } } } int ans=0; for(int i=0;i<sa.idx;i++) { add(ans,dp[L][i][0]); } return ans; } int main() { rev['A']=0; rev['C']=1; rev['G']=2; rev['T']=3; int m,L; while(cin>>L>>m) { sa.init(); for(int i=1;i<=m;i++) { cin>>word; sa.Insert(sa.root,word,strlen(word)); } sa.acbuild(sa.root); printf("%d\n",solve(L)); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。