正題

題目鏈接:https://www.luogu.com.cn/problem/P3041

---

題目大意

輸入$n$個(gè)只有$ABC$的字符串，求一個(gè)長度為$L$的字符串中最多包含多少個(gè)子串是$n$個(gè)字符串中的一個(gè)

---

解題思路

考慮$AC$自動(dòng)機(jī)是如何進(jìn)行匹配的，對于下一個(gè)字符，如果有路便往那個(gè)方向走去，然后統(tǒng)計(jì)該點(diǎn)沿條$fail$到根節(jié)點(diǎn)所經(jīng)過所有節(jié)點(diǎn)的值。然后如果沒有繼續(xù)往下走的路了就跳到該節(jié)點(diǎn)的$fail$繼續(xù)走（因?yàn)樵谇?span id="ze8trgl8bvbq" class="katex--inline">$fail$的時(shí)候已經(jīng)修改的$Trie$樹上的數(shù)組，其實(shí)是可以直接往后走的）。

之后我們就有了$dp$的方法，$va{l}_i$表示在$fail$樹上$i$節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑上有多少個(gè)串的結(jié)束位置。$f_{i,j}$表示現(xiàn)在填字符的$i$個(gè)位置，目前在$Trie$樹上節(jié)點(diǎn)為$j$的最大答案。之后進(jìn)行$dp$即可

時(shí)間復(fù)雜度$O(3?{\sum }_{i=1}^n|s_i|L)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=2100; int n,L,cnt,ans; int val[N],son[N][3],fail[N],f[N][N]; char s[N]; queue<int> q; void Make(char *s){int x=0,len=strlen(s);for(int i=0;i<len;i++){int c=s[i]-'A';if(!son[x][c])son[x][c]=++cnt;x=son[x][c];}val[x]++;return; } void Get_Fail(){for(int i=0;i<3;i++)if(son[0][i])q.push(son[0][i]);while(!q.empty()){int x=q.front();q.pop();for(int i=0;i<3;i++)if(!son[x][i])son[x][i]=son[fail[x]][i];else{q.push(son[x][i]);int y=fail[x];fail[son[x][i]]=son[y][i];}val[x]+=val[fail[x]];}return; } int main() {scanf("%d%d",&n,&L);for(int i=1;i<=n;i++){scanf("%s",s);Make(s);}Get_Fail();memset(f,0xcf,sizeof(f));f[0][0]=0;for(int i=1;i<=L;i++)for(int j=0;j<=cnt;j++)for(int k=0;k<3;k++){f[i][son[j][k]]=max(f[i][son[j][k]],f[i-1][j]+val[son[j][k]]);if(i==L)ans=max(ans,f[i][son[j][k]]);}printf("%d",ans); }

總結(jié)

以上是生活随笔為你收集整理的P3041-[USACO12JAN]Video Game G【AC自动机,dp】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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