在字符串末尾插入的最小字符数，使其成为回文 [英] Minimum number of characters to be inserted at the end of a string to make it a palindrome

问题描述

问题是这样的 -

我们必须在字符串的末尾找到要插入的最小字符数使它成为一个回文。

We have to find the minimum number of characters to be inserted at the end of a string to make it a palindrome.

所以，在我努力做这个问题，我认为这相当于找到最大的回文子字符串，也是后缀字符串。

So, in my efforts to do this problem, I figured that this is equivalent to finding the largest palindromic substring which is also a suffix of the string.

我可以轻松地在O（n ^ 2）中执行此操作，但我正在寻找一个可能使用修改后的KMP的O（n）解决方案。有人请帮我弄清楚。

I could do this in O(n^2) easily but I am looking for a O(n) solution which is probably possible using modified KMP. Somebody please help me figure out.

推荐答案

我有一种使用散列作为答案的方法这里。

I have an approach that uses hashing posted as an answer here.

你也可以使用KMP。您可以为反转的字符串计算前缀函数，然后从左到右迭代初始字符串：

You can indeed also use KMP. You can compute the prefix function for the reversed string, and then iterate your initial string from left to right:

KMP计算函数 prefix [i] =作为字符串[1..i]后缀的字符串的最长前缀

但是，我们想知道我们的字符串最长的后缀是反转字符串的前缀。为什么？如果我们有：

However, we want to know the longest suffix of our string that is a prefix of the reversed string. Why? If we have:

15232 => reverse = 23251

然后，作为反转字符串前缀的字符串的最长后缀为 232 。这是一个回文，它让我们找到你所要求的内容，因为如果两个是回文，则字符串的后缀与反转字符串的前缀重叠。

Then the longest suffix of the string that is a prefix of the reversed string is 232. This is a palindrome, and it lets us find what you're asking because a suffix of the string overlaps a prefix of the reversed string if the two are palindromes.

你有以下情况：

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算法。

So it suffices to compute the prefix function of the KMP algorithm.

这篇关于在字符串末尾插入的最小字符数，使其成为回文的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！