algorithm - 找到要在字符串中添加使其成为回文的最少字符数

Question

这是spoj的问题。 AIBOHP

字符可以添加到字符串的任意位置。
我读到的最简单的解决方案如下:
找到字符串的Longest Common Subsequence 并且它是反向的。那么答案是(字符串的长度 - 两个字符串的 LCS)。这种看起来很直观，但我很难证明这一点。如果这个问题看起来很愚蠢，我很抱歉，但有人可以清楚地解释为什么这种方法总是有效。

注意:有时会在 Stack Overflow 上询问与此问题相关的问题，但似乎没有一个能回答我的问题。这个问题不重复，在this问题答案说明了这种方法，但没有给出直觉或证据，而这正是我要问的。我知道如何解决它，我在问为什么这种方法有效。

Answer 1

让我们认识到，您的 LCS 只不过是原始输入的最长子回文(不一定是连续的)。如果 x 是最长子回文中不的字母数，您可以轻松地将 2x 添加到该子回文中使其成为包含您的原始输入并保持回文。

考虑单词 berries 写成 bERRiEs，大写字母表示最长的子回文，ERRE。从中间开始，为原始单词中的每个小写字母添加 2 个字母:ERRE -> EiRRiE -> bEiRRiEb -> sbEiRRiEbs 然后就可以了。

另一方面，这无法改进。假设您在输入中添加了 y 字符以使其成为回文。删除 2y 字符(添加的字符及其镜像)以获得输入序列的子回文 - 这显然不能大于最长的子回文，因此您至少添加了缺失的数量最长子回文中的字符。