第一篇题解在使用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 数组找到一个完整的周期,为什么这么做是对的