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

Question

例如字符串“ abaccddccefe”中的“ ccddcc”我想到了一个解决方案，但它的运行时间为O（n ^ 2）算法1：步骤：这是一种蛮力方法对于i = 1至i小于array.length的2个for循环，对于j = i + 1至j小于 array.length的-1这样，您可以从数组中获取所有可能组合的子字符串具有回文功能，可检查字符串是否为回文因此，对于每个子字符串（i，j）都调用此函数（如果它是回文）将其存储在字符串变量中如果找到下一个回文子字符串，并且该子字符串大于当前子字符串，则将其替换为当前子字符串。最后，您的字符串变量将得到答案问题：1.该算法运行时间为O（n ^ 2）。算法2：反转字符串并将其存储在不同的数组中现在找到两个数组之间最大的匹配子字符串但这也需要O（n ^ 2）时间你们能想到一种运行时间更好的算法吗？如果可能的话O（n）时间

Answer 1

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

对于输入，String s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE"它将找到正确的输出1234567887654321。

Answer 2

据我了解的问题，我们可以在中心索引附近找到回文，并在中心的左右两侧进行搜索。鉴于此，并且知道输入的角落没有回文，我们可以将边界设置为1和length-1。注意字符串的最小和最大边界时，我们验证对称索引位置（右和左）上的字符对于每个中心位置是否都相同，直到达到最大上限中心。

外循环为O（n）（最多n-2次迭代），内循环为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