一个并不需要 KMP 的(2)O(n2) 算法。显然要考虑 dp。与 KMP 方法不同的是我们不考虑加入一个数的贡献而是考虑从一个点为起点的目标字符串串前缀的贡献。那么状态里需要记录一下目前已经确定了前面几位以及接下来应该考虑的转移位置。下一个转移位置应该是范围不被前面的串限制住的也就是它可以与现在所有已经确定的匹配。预处理出目标字符串的某一位为起点可以一直匹配到目标字符串的哪里。之后我们枚举目标字符串加入的前缀长度并且找到之后第一个可以一直匹配到前缀最后的位置记录到 pos 中把在此之前的部分为起点的贡献加入 ‘sum’ 中。dp 时记录目前子弹字符串长度和目前已经匹配结束的子弹字符串前缀。之后我们就可以通过 pos 得到下一次转移的匹配结束的子弹字符串前缀长度通过 sum 计算贡献。设,dpi,j​表示匹配结束的子弹字符串前缀长度为i目前子弹字符串长度为j枚举k。可以得到转移式:−−1,max⁡(,−)dpposk−i​i−1,k​max(dpi,j​sumk−i​)显然可以给,dpi,j​取最大值将时间复杂度压缩至(2)O(n2)。需要注意我们没有考虑之前的起始位置受新的起始位置产生的字符影响而产生的贡献因为如果有贡献可以在自身决策时就这样选择所以答案不受影响。代码cpp#includebits/stdc.h#define int long longusing namespace std;char s[2005];int m,n,len[2005],pos[2005],sum[2005],dp[2005][2005];signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cins1;mstrlen(s1);cinn;for(int i1;im;i){len[i]i-1;for(int j1,wi;wm;j,w){if(s[j]!s[w])break;len[i]w;}}for(int i1;im;i){pos[i]i1;for(int j1;ji;j){if(j!1len[j]i){pos[i]j;break;}sum[i]min(len[j]-j1,i-j1);}}memset(dp,-0x3f,sizeof(dp));dp[0][0]0;for(int i0;in;i){int ma-1e16;for(int ki;kmin(n,im);k){mamax(ma,dp[i][k]);if(k!i)dp[pos[k-i]-1i][k]max(dp[pos[k-i]-1i][k],masum[k-i]);}}coutdp[n][n];return 0;}