Readme

2430.Maximum-Deletions-on-a-String

因为是一刀一刀地从头开始砍，显然我们会令dp[i]表示以i开头的字符串的maximum deletion。

对于状态的转移，我们不难想到尝试它的第一个刀的位置。假设我们想砍在位置j之前，那么就需要查看是否满足[i:j-1]和[j:j+j-i]这两段区间是否相等。如果是的话，就有dp[i] = d[j]+1.

那么如何高效判断这两个分别以i和j开头的区间是否相等呢？我们可以用N^2的时间预处理，先得到任意两个位置i和j的最大公共前缀长度lcs。如果lcs[i][j] >= j-i，那么就意味着[i:j-1]和[j:j+j-i]这两段区间必然相等。事实上，对于i而言可能会有多个合适的j，所以dp[i] = max{d[j]+1}

最终返回dp[0].