要在字符串末尾插入的最小字符数,以使其成为回文

Question

问题是这样的 -

我们必须找到要在字符串末尾插入的最小字符数,以使其成为回文.

因此,在我努力解决这个问题时,我认为这相当于找到最大的回文子串,这也是字符串的后缀.

我可以很容易地在O(n ^ 2)中做到这一点,但我正在寻找可能使用改进的KMP的O(n)解决方案.有人请帮我搞清楚.

Answer 1

我有一种方法,在这里使用散列作为答案发布.

你确实也可以使用KMP.您可以计算反向字符串的前缀函数,然后从左到右迭代您的初始字符串:

KMP计算一个函数 prefix[i] = longest prefix of the string that is a suffix of string[1..i]

但是,我们想知道the longest suffix of our string that is a prefix of the reversed string.为什么？如果我们有:

15232 => reverse = 23251

然后,作为反转字符串前缀的字符串的最长后缀是232.这是一个回文,它让我们找到你要问的东西,因为如果两个是回文,那么字符串的后缀会与反向字符串的前缀重叠.

你有这样的情况:

prefix[i] = length - i => you can get a palindrome of 
            length 2*prefix[i] centered at i and i+1

prefix[i] = length - i + 1 => you can get a palindrome of
            length 2*prefix[i] - 1 centered at i

prefix[i] < length - i => you can't have a palindrome, ignore this position

因此,计算KMP算法的前缀函数就足够了.