如何获得字符串的最短回文

Question

例如：

字符串是：abcd

最短回文是abcdcba

较长回文可以是：abcddcba

又如：字符串

：aaaab

最短回文是aaaabaaaa

较长回文可以是aaaaabbaaaa

限制：只能在最后添加字符。

Answer 1

只需将字符串的初始子字符串从最短到最长的反向附加到字符串中，直到得到回文。例如，对于“acbab”，尝试附加“a”，它产生“acbaba”，它不是回文，然后尝试附加“ac”反向，产生“acbabca”，它是回文。

更新：请注意，您不必实际执行附加操作。您知道子字符串匹配，因为您刚刚反转了它。因此，您所要做的就是检查字符串的其余部分是否是回文，如果是，则附加子字符串的反向内容。这是皮蒂瓦尔象征性地写下的内容，所以他可能应该得到答案。示例：对于“acbab”，找到最长的回文后缀；那是“bab”。然后反向附加余数“ac”：ac bab ca。

Answer 2

我对逻辑的猜测：

假设你的字符串是 [a1...an] （字符 a1 到 an 的列表）

• 找到最小的 i 使得 [ai...an] 是一个回文。
• 最小的回文是 [a1 ... a(i-1)] ++ [ai ... an] ++ [a(i-1) ... a1]

，其中 ++ 表示字符串连接。

Answer 3

一些伪代码，至少给你留下一些工作：

def shortPalindrome(s):
  for i in range(len(s)):
    pal = s + reverse(s[0:i])
    if isPalindrome(pal):
      return pal
  error()

Answer 4

Python 代码，应该很容易转换为 C：

for i in range(1, len(a)):
    if a[i:] == a[i:][::-1]:
        break
print a + a[0:i][::-1]

Answer 5

最近我也被问到了同样的问题，以下是我在采访中写的内容：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int isPalin ( char *str ) {
    int i, len=strlen(str);
    for (i=0; i<len/2; ++i)
        if (str[i]!=str[len-i-1])
            break;
    return i==len/2;
}

int main(int argc, char *argv[]) {
    if (argc!=2)
        puts("Usage: small_palin <string>");
    else {
        char *str = argv[1];
        int i=0, j, len=strlen(str);
        while ( !isPalin(str+i) )
            ++i;
        char *palin = malloc(len+1+i);
        *(palin+len+1+i) = '\0';
        strcpy(palin,str);
        for (i=i-1, j=0; i>=0; --i, ++j)
            *(palin+len+j) = str[i];
        puts(palin);
    }
    return 0;
}

我觉得如果我编写一个 strrev() 函数并使用 strcmp() 检查回文，程序会更加结构化。这将使我能够反转源字符串的起始字符并使用 strcpy() 直接复制它。

我采用这个解决方案的原因是，在这个问题之前，我被要求检查回文，并且我已经在纸上写下了 isPalin() 。感觉使用现有的代码会更好！

Answer 6

从您显示的示例来看，最长的回文是原始字符串与其反向连接，最短的回文是原始字符串与其反向连接（除了第一个字符之外）。但我很确定你想要更复杂的东西。也许你可以举出更好的例子？

Answer 7

如果字符串由 k 个字符组成，我认为您应该向该字符串添加反转的 (k-1) 个字符...

Answer 8

以下是我对另一种情况的回答：通过在前面附加字符来实现最短回文。所以你的任务是理解算法并适当修改它。
基本上，它指出通过在字符串 s 的前面添加一些字符来找到最短的回文。

如果你从来没有尝试过解决这个问题，我建议你去解决它，它会帮助你提高解决问题的能力。

解决之后我一直在寻找更好的解决方案。我偶然发现了另一个程序员的解决方案。它是用Python编写的，而且非常简洁。确实很有趣，但是后来我发现这是错误的。

class Solution:
    # @param {string} s
    # @return {string}
    def shortestPalindrome(self, s):
        A=s+s[::-1]
        cont=[0]
        for i in range(1,len(A)):
            index=cont[i-1]
            while(index>0 and A[index]!=A[i]):
                index=cont[index-1]
            cont.append(index+(1 if A[index]==A[i] else 0))
        print cont[-1]
        return s[cont[-1]:][::-1]+s

我本人查看了该解决方案并发现了一个有趣的想法。首先，该算法连接字符串及其反转版本。接下来的步骤与 KMP 算法中使用的构建 KMP 表（或失效函数）的步骤类似。为什么这个程序有效？

如果您了解 KMP 文本搜索算法，您就会知道它的“查找表”以及构建它的步骤。现在，我只展示该表的一个重要用途：它可以显示字符串 s 的最长前缀，该前缀也是 s 的后缀（但不是 s 本身）。例如，“abcdabc”具有最长的前缀，它也是后缀：“abc”（不是“abcdabc”，因为这是整个字符串！！！）。为了让它变得有趣，我们称这个前缀为 s 的“快乐子串”。因此，“aaaaaaaaaa”（10 个 a）的快乐子串是“aaaaaaaaa”（9 个 a）。

现在我们回过头来看看找到 s 的快乐子串如何帮助解决最短回文问题。

假设q是添加到s前面使字符串qs成为回文的最短字符串。我们可以看到显然 length(q) < length(s) 因为 ss 也是回文。由于 qs 是回文，因此 qs 必须以 q 结尾，或者 s = p+q，其中 p 是 s 的子串。我们很容易看出 p 也是一个回文。因此，为了获得最短的 qs，q 必须最短。反过来，p 是 s 的最长回文子串。

我们称s'和q'分别是s和q的反转字符串。我们看到 s = pq, s' = q'p 因为 p 是回文。所以 ss' = pqq'p 。现在我们需要找到最长的p。尤里卡！这也意味着 p 是字符串 ss' 的快乐子字符串。这就是上面的算法的工作原理！

但经过一番思考，上述算法存在一些漏洞。 p 不是 ss' 的快乐子串！事实上，p是最长的前缀，也是ss'的后缀，但前缀和后缀不能互相重叠。所以让我们变得更有趣，我们称字符串 s 的“非常快乐的子串”是 s 的最长子串，它既是前缀，也是后缀，并且这个前缀和后缀不能重叠。换句话说，s的“极乐子串”的长度必须小于或等于s的一半长度。

所以事实证明 ss' 的“快乐子串”并不总是 ss' 的“极其快乐子串”。我们可以很容易地构造一个例子：s = "aabba"。 ss'=“aabbaabbaa”。 “aabbaabbaa”的快乐子串是“aabbaa”，而“aabbaabbaa”的极其快乐子串是“aa”。砰!

因此，基于 length(p) <= length(ss')/2 的观察，正确的解决方案应如下所示。

class Solution:
    # @param {string} s
    # @return {string}
    def shortestPalindrome(self, s):
        A=s+s[::-1]
        cont=[0]
        for i in range(1,len(A)):
            index=cont[i-1]
            while(index>0):
                if(A[index]==A[i]):
                    if index < len(s):
                        break
                index=cont[index-1]
            cont.append(index+(1 if A[index]==A[i] else 0))
        print cont[-1]
        return s[cont[-1]:][::-1]+s 

万岁！
正如你所看到的，算法很有趣！

我写的文章的链接此处

Answer 9

看起来这里概述的解决方案是 O(N^2)（对于反转字符串 S 的每个后缀 X，查找 S + X 是否是回文）。

我相信这个问题有一个线性的，即 O(N) 解决方案。考虑以下语句：唯一需要附加比 S.Length - 1 少的字符的情况是字符串已包含部分回文，因此它将采用 NNNNNPPPPPP 的形式，其中 PPPPPP 表示回文。这意味着，如果我们能找到最大的尾随回文，我们可以通过将 NNNNN 的反向连接到末尾来线性解决它。

最后，存在一个著名的算法（Manacher，1975），它可以找到字符串中包含的最长（实际上是全部）回文（有一个很好的解释 此处）。可以轻松修改它以返回最长的尾随回文，从而为该问题提供线性解决方案。

如果有人感兴趣，这里是镜像问题的完整代码（在开头附加字符）：

   using System.Text;

    // Via http://articles.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
    class Manacher
    {
        // Transform S into T.
        // For example, S = "abba", T = "^#a#b#b#a#$".
        // ^ and $ signs are sentinels appended to each end to avoid bounds checking
        private static string PreProcess(string s)
        {
            StringBuilder builder = new StringBuilder();

            int n = s.Length;
            if (n == 0) return "^$";

            builder.Append('^');

            for (int i = 0; i < n; i++)
            {
                builder.Append('#');
                builder.Append(s[i]);
            }

            builder.Append('#');
            builder.Append('

);

            return builder.ToString();
        }

        // Modified to return only the longest palindrome that *starts* the string
        public static string LongestPalindrome(string s)
        {
            string T = PreProcess(s);
            int n = T.Length;
            int[] P = new int[n];
            int C = 0, R = 0;
            for (int i = 1; i < n - 1; i++)
            {
                int i_mirror = 2 * C - i; // equals to i' = C - (i-C)

                P[i] = (R > i) ? Math.Min(R - i, P[i_mirror]) : 0;

                // Attempt to expand palindrome centered at i
                while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
                    P[i]++;

                // If palindrome centered at i expand past R,
                // adjust center based on expanded palindrome.
                if (i + P[i] > R)
                {
                    C = i;
                    R = i + P[i];
                }
            }

            // Find the maximum element in P.
            int maxLen = 0;
            int centerIndex = 0;
            for (int i = 1; i < n - 1; i++)
            {
                if (P[i] > maxLen 
                    && i - 1 == P[i] /* the && part forces to only consider palindromes that start at the beginning*/)
                {
                    maxLen = P[i];
                    centerIndex = i;
                }
            }

            return s.Substring((centerIndex - 1 - maxLen) / 2, maxLen);
        }
    }
    
public class Solution {
    public string Reverse(string s)
    {
        StringBuilder result = new StringBuilder();
        for (int i = s.Length - 1; i >= 0; i--)
        {
            result.Append(s[i]);
        }
        return result.ToString();
    }
    

        public string ShortestPalindrome(string s)
        {
            string palindrome = Manacher.LongestPalindrome(s);
            string part = s.Substring(palindrome.Length);
            return Reverse(part) + palindrome + part;
        }
}

Answer 10

    using System;
    using System.Collections.Generic;
    using System.Linq;
    public class Test
    {

    public static void shortPalindrome(string [] words){
    List<string> container = new List<string>(); //List of Palindromes

    foreach (string word in words )
    {
        char[] chararray = word.ToCharArray();
        Array.Reverse(chararray);
        string newText = new string(chararray);

        if (word == newText) container.Add(word); 
    }

    string shortPal=container.ElementAt(0);
    for(int i=0; i<container.Count; i++)
    {
        if(container[i].Length < shortPal.Length){
            shortPal = container[i];
        }

    }

    Console.WriteLine(" The Shortest Palindrome is {0}",shortPal);

    }

    public static void Main()
    {
    string[] word = new string[5] {"noon", "racecar","redivider", "sun", "loss"};
    shortPalindrome(word);
    }
    }

Answer 11

最短回文 -

• 从最后一个位置 + 1 反向迭代到开头
• Push_back 元素

---

#include <iostream>
#include <string>
using namespace std ;

int main()
{
    string str = "abcd" ;
    string shortStr = str ;
    for( string::reverse_iterator it = str.rbegin()+1; it != str.rend() ; ++it )
    {
        shortStr.push_back(*it) ;   
    }
    cout << shortStr << "\n" ;
}

更长的回文可以更长。

例如：abcd
更长的回文 - abcddcba, abcdddcba, ...