題目大意

題目大意：給定有ABC組成的串n個，然后請你生成一個長度為K的串求給定的串在生成串中最多被匹配時的次數

分析

AC自動機模板題。
構建trie，然后DP.
p是當前節點，l是已經構造的串的長度。
沒有保存father，可以使用刷表法。
f[p->ch][l]=max(f[p][l-1],f[p->ch][l])+p->ch->cnt;
f[p->fail][l]=max(f[p][l],f[p->fail][l]);

代碼

#include<cstdio> #include<cstring> #include<queue> #include<cassert> #include<algorithm> #define MAXN 20 #define MAXLEN 15 #define MAXC 26 #define MAXK 2000 using namespace std; int n,k,len; void Read(int &x){char c;while(c=getchar(),c!=EOF)if(c>='0'&&c<='9'){x=c-'0';while(c=getchar(),c>='0'&&c<='9')x=x*10+c-'0';ungetc(c,stdin);return;} } struct node{int cnt;node *ch[MAXC],*fail;int f[MAXK+2]; }tree[MAXN*MAXLEN+10],*tcnt=tree,*root=tree; queue<node*>q; void init(){char s[MAXLEN+10];Read(n),Read(k);int i,j;node *p;for(j=1;j<=n;j++){scanf("%s",s);p=root;for(i=0;s[i];i++){s[i]-='A';if(!p->ch[s[i]]){p->ch[s[i]]=++tcnt;memset(p->ch[s[i]]->f,0x80,sizeof p->ch[s[i]]->f);}p=p->ch[s[i]];}p->cnt++;} } void ACbuild(){int i;node *p,*bef;for(i=0;i<MAXC;i++)if(root->ch[i]){root->ch[i]->fail=root;q.push(root->ch[i]);}while(!q.empty()){p=q.front();q.pop();for(i=0;i<MAXC;i++)if(p->ch[i]){for(bef=p->fail;bef;bef=bef->fail)if(bef->ch[i]){p->ch[i]->fail=bef->ch[i];break;}if(!bef)p->ch[i]->fail=root;p->ch[i]->cnt+=p->ch[i]->fail->cnt;q.push(p->ch[i]);}} } void dp(){int i,j;node *p,*bef;for(i=1;i<=k;i++){q.push(root);while(!q.empty()){p=q.front();q.pop();p->f[i]+=p->cnt;for(j=0;j<MAXC;j++)if(p->ch[j]){p->ch[j]->f[i]=max(p->f[i-1],p->ch[j]->f[i]);q.push(p->ch[j]);}for(bef=p->fail;bef;bef=bef->fail)bef->f[i]=max(p->f[i],bef->f[i]);}} } int main() {init();ACbuild();dp();printf("%d\n",root->f[k]); }

總結

以上是生活随笔為你收集整理的【AC自动机+DP】[USACO JAN2012 GOLD Problem 1: Video Game Combos]的全部內容，希望文章能夠幫你解決所遇到的問題。

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