題目的匹配應該也要看成一個文本串與另一個模式串的匹配過程
Text是以當前i結尾的后綴來匹配Pattern的前綴(非真)
這里的Pattern肯定是可以匹配成功的,直接由next來保證(next總是當前結尾的最大前綴,恰好滿足遞推的需要)
(說的不是很準確,就是kmp匹配過程時使用的方法)
舉個栗子:
a b a b a c b a

0 0 1 2 3 0 0 1 next
1 1 1 1 1 1 1 1 dp 初始合法狀態
1 1 2 2 3 1 1 2 dp 最終計算結果

dp[1] = 1+dp[next[1]] : Text aPattern a dp[2] = 1+dp[next[2]]:Text abPattern ab dp[3] = 1+dp[next[3]] = 1+dp[1]:Text abaPattern aba a dp[4] = 1+dp[2]:Text ababPattern abab ab dp[5] = 1+dp[3]:Text ababaPattern ababa aba a .... dp[8] = 1+dp[1]:Text ababacbaPattern ababacba a

最終統計得到
4 a
2 ab
2 aba
1 abab
1 ababa
1 ababac
1 ababacb
1 ababacba

這種以【當前狀態】來轉換角度的統計方法值得學習
所以說動態規劃天下第一(明明是遞推

/*H E A D*/ int nxt[maxn]; char P[maxn]; int dp[maxn];//dp[i]:P[i]結尾的子串所含滿足匹配的前綴的個數 void buildNext(){nxt[1]=0;int j=0;int m=strlen(P+1);rep(i,2,m){while(j>0&&P[i]!=P[j+1]) j=nxt[j];if(P[i]==P[j+1]) j++;nxt[i]=j;dp[i]=1+dp[j];} } int main(){int t=read();while(t--){int n=read();s1(P);dp[0]=0;rep(i,1,n) dp[i]=1;buildNext();ll sum=0;rep(i,1,n) sum=(sum+dp[i])%10007;println(sum); }return 0; }

轉載于:https://www.cnblogs.com/caturra/p/8435770.html

總結

以上是生活随笔為你收集整理的HDU - 3336 next运用+递推的全部內容，希望文章能夠幫你解決所遇到的問題。

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