编写一个返回给定字符串中最长回文的函数

Question

例如字符串"abaccddccefe"中的"ccddcc"

我想到了一个解决方案,但它在O(n ^ 2)时间运行

Algo 1:

步骤:它是一种强力方法

1. 对于j = i + 1到j小于array.length,
   对于i = 1到i小于array.length -1
   , 有2个for循环
2. 这样,您可以从数组中获取每个可能组合的子字符串
3. 有一个回文功能,检查字符串是否是回文
4. 所以对于每个子串(i,j)调用这个函数,如果它是一个回文存储它在一个字符串变量中
5. 如果您找到下一个回文子串并且如果它大于当前回归,则将其替换为当前的回归.
6. 最后你的字符串变量将有答案

问题:1.这个算法在O(n ^ 2)时间运行.

算法2:

1. 反转字符串并将其存储在不同的数组中
2. 现在找到两个数组之间最大的匹配子字符串
3. 但这也是在O(n ^ 2)时间内运行的

你们能想到一个在更好的时间里运行的算法吗？如果可能的话O(n)时间

Answer 1

您可以使用最长的回文Manacher算法的O(n)时间!它的实现可以在这里和这里找到.

对于输入,String s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE"它找到正确的输出1234567887654321.

Answer 2

Algo 2可能不适用于所有字符串.以下是此类字符串"ABCDEFCBA"的示例.

不是字符串有"ABC"和"CBA"作为其子字符串.如果您反转原始字符串,它将是"ABCFEDCBA".并且最长的匹配子串是"ABC",它不是回文.

您可能需要另外检查这个最长匹配的子串是否实际上是一个运行时间为O(n ^ 3)的回文.

Answer 3

据我所知,我们可以找到围绕中心索引的回文,并在中心的左右两侧搜索我们的搜索.鉴于并且知道输入的角落没有回文,我们可以将边界设置为1和长度-1.在注意字符串的最小和最大边界的同时,我们验证对称索引(右和左)位置处的字符是否对于每个中心位置是相同的,直到我们达到最大上限中心.

外环是O(n)(最多n-2次迭代),内部while循环是O(n)(最大值约为(n/2)-1次迭代)

这是我使用其他用户提供的示例的Java实现.

class LongestPalindrome {

    /**
     * @param input is a String input
     * @return The longest palindrome found in the given input.
     */
    public static String getLongestPalindrome(final String input) {
        int rightIndex = 0, leftIndex = 0;
        String currentPalindrome = "", longestPalindrome = "";
        for (int centerIndex = 1; centerIndex < input.length() - 1; centerIndex++) {
            leftIndex = centerIndex - 1;  rightIndex = centerIndex + 1;
            while (leftIndex >= 0 && rightIndex < input.length()) {
                if (input.charAt(leftIndex) != input.charAt(rightIndex)) {
                    break;
                }
                currentPalindrome = input.substring(leftIndex, rightIndex + 1);
                longestPalindrome = currentPalindrome.length() > longestPalindrome.length() ? currentPalindrome : longestPalindrome;
                leftIndex--;  rightIndex++;
            }
        }
        return longestPalindrome;
    }

    public static void main(String ... args) {
        String str = "HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE";
        String longestPali = getLongestPalindrome(str);
        System.out.println("String: " + str);
        System.out.println("Longest Palindrome: " + longestPali);
    }
}

输出结果如下:

marcello:datastructures marcello$ javac LongestPalindrome
marcello:datastructures marcello$ java LongestPalindrome
String: HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE
Longest Palindrome: 12345678987654321

Answer 4

最近有人问我这个问题。这是我[最终]想出的解决方案。我用 JavaScript 来做，因为用那种语言来说它非常简单。

基本概念是遍历字符串寻找可能的最小多字符回文（两个或三个字符的回文）。一旦完成，扩大两侧的边界，直到它不再是回文。如果该长度比当前最长的长度长，则将其存储并继续移动。

// This does the expanding bit.
function getsize(s, start, end) {
    var count = 0, i, j;
    for (i = start, j = end; i >= 0 && j < s.length; i--, j++) {
        if (s[i] !== s[j]) {
            return count;
        }
        count = j - i + 1; // keeps track of how big the palindrome is
    }
    return count;
}

function getBiggestPalindrome(s) {
    // test for simple cases
    if (s === null || s === '') { return 0; }
    if (s.length === 1) { return 1; }
    var longest = 1;
    for (var i = 0; i < s.length - 1; i++) {
        var c = s[i]; // the current letter
        var l; // length of the palindrome
        if (s[i] === s[i+1]) { // this is a 2 letter palindrome
            l = getsize(s, i, i+1);
        }
        if (i+2 < s.length && s[i] === s[i+2]) { // 3 letter palindrome
            l = getsize(s, i+1, i+1);
        }
        if (l > longest) { longest = l; }
    }
    return longest;
}

这肯定可以进一步清理和优化，但除了最坏的情况（同一字母的字符串）之外，它在所有情况下都应该具有相当好的性能。