关于本题KMP解法的问题
查看原帖
关于本题KMP解法的问题
713562
hahaxiang楼主2024/10/8 15:10

第一篇题解在使用KMP优化DP时写了如下代码

if(j%(j-Next[j]) == 0) dp[j+i] = min(dp[j+i], dp[i]+cnt[j/(j-Next[j])]+(j-Next[j]));
        else dp[j+i] = min(dp[j+i], dp[i]+1+j);

问题是,当(j-Next[j])不是一个完整的周期时,还可以通过继续跳 Next 数组找到一个完整的周期,为什么这么做是对的

2024/10/8 15:10
加载中...