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

Question

例如 :

字符串是:abcd

最短的回文是abcdcba是解决方案

较长的回文可以是:abcddcba

另一个例子:

字符串:aaaab

最短的回文是aaaabaaaa

较长的回文可以是aaaaabbaaaa

限制:您最后只能添加字符.

Answer 1

只需将字符串的初始子串(从最短到最长)的反向追加到字符串,直到你有一个回文.例如,对于"acbab",尝试附加"a",其产生"acbaba",这不是回文,然后尝试附加"ac"反转,产生"acbabca",这是一个回文.

更新:请注意,您不必实际执行追加.你知道子串匹配,因为你只是颠倒了它.因此,您所要做的就是检查字符串的其余部分是否为回文,如果是,则追加子字符串的反向.这是Ptival象征性地写的,所以他应该得到答案的功劳.示例:对于"acbab",找到最长的后缀,即回文; 那就是"bab".然后将剩余部分"ac"反向追加:ac bab ca.

Answer 2

我对逻辑的猜测:

假设你的字符串是[a1 ... an](字符a1到a的列表)

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

其中++表示字符串连接.