一个并不需要 KMP 的
�
(
�
2
)
O(n
2
) 算法。

显然要考虑 dp。

与 KMP 方法不同的是，我们不考虑加入一个数的贡献，而是考虑从一个点为起点的目标字符串串前缀的贡献。

那么状态里需要记录一下目前已经确定了前面几位，以及接下来应该考虑的转移位置。

下一个转移位置应该是范围不被前面的串限制住的，也就是它可以与现在所有已经确定的匹配。

预处理出目标字符串的某一位为起点可以一直匹配到目标字符串的哪里。

之后，我们枚举目标字符串加入的前缀长度，并且找到之后第一个可以一直匹配到前缀最后的位置记录到 pos 中，把在此之前的部分为起点的贡献加入 ‘sum’ 中。

dp 时，记录目前子弹字符串长度和目前已经匹配结束的子弹字符串前缀。

之后，我们就可以通过 pos 得到下一次转移的匹配结束的子弹字符串前缀长度，通过 sum 计算贡献。

设
�
�
�
,
�
dp
i,j
​
表示匹配结束的子弹字符串前缀长度为
�
i，目前子弹字符串长度为
�
j，枚举
�
k。

可以得到转移式:

�
�
�
�
�
�
−
�
+
�
−
1
,
�

max
⁡
(
�
�
�
,
�
+
�
�
�
�
−
�
)
dp
pos
k−i
​
+i−1,k
​
=max(dp
i,j
​
+sum
k−i
​
)
显然可以给
�
�
�
,
�
dp
i,j
​
取最大值，将时间复杂度压缩至
�
(
�
2
)
O(n
2
)。

需要注意，我们没有考虑之前的起始位置受新的起始位置产生的字符影响而产生的贡献，因为如果有贡献可以在自身决策时就这样选择，所以答案不受影响。

代码：

cpp
#include<bits/stdc++.h>
#define int long long
using 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);
cin>>s+1;m=strlen(s+1);
cin>>n;
for(int i=1;i<=m;i++){
len[i]=i-1;
for(int j=1,w=i;w<=m;j++,w++){
if(s[j]!=s[w])break;
len[i]=w;
}
}
for(int i=1;i<=m;i++){
pos[i]=i+1;
for(int j=1;j<=i;j++){
if(j!=1&&len[j]>=i){
pos[i]=j;
break;
}
sum[i]+=min(len[j]-j+1,i-j+1);
}
}
memset(dp,-0x3f,sizeof(dp));
dp[0][0]=0;
for(int i=0;i<n;i++){
int ma=-1e16;
for(int k=i;k<=min(n,i+m);k++){
ma=max(ma,dp[i][k]);
if(k!=i)dp[pos[k-i]-1+i][k]=max(dp[pos[k-i]-1+i][k],ma+sum[k-i]);
}
}
cout<<dp[n][n];
return 0;
}