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

Question

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

104

例如，在字符串“abaccddccefe”中寻找“ccddcc”。

我想到了一种解法，但是它的时间复杂度为O(n^2)。

算法1: 步骤: 这是一种暴力方法 1. 有两个for循环对于i = 1到i小于array.length-1 对于j=i+1到j小于array.length 2. 这样就可以从数组中获得每个可能组合的子串。 3. 拥有一个回文函数来检查一个字符串是否是回文的。 4. 因此，对于每个子串(i,j)，调用此函数，如果它是回文的，则将其存储在一个字符串变量中。 5. 如果你发现下一个回文子串大于当前子串，则用当前子串替换它。 6. 最后，您的字符串变量将具有答案。

问题： 1. 这个算法的时间复杂度为O(n^2)。

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

你们能想出一个更好的算法吗？如果可能的话，请使用O(n)时间。

- Learner

44

我认为第一种方法需要O(n^2)的时间来获取所有子字符串，再需要O(n)的时间检查它们是否是回文，总共需要O(n^3)的时间复杂度？ - Skylar Saveland

如果我知道我正在处理回文，并将我的字符串保存为两半，那么如果我使用Java，我将拥有O(1)函数检查，对吗？ - viki.omega9

10

第二个算法正确吗？那么对于字符串："abcdecba"，最大的匹配子串是什么呢("abcdecba" vs. "abcedcba")? "abc" 或者 "cba"。然而，这两个都不是回文。 - Yarneo

@Learner，只是好奇，在你上面的步骤中，你在for循环中引用了哪个数组？你所指的数组是指字符串吗？string.length？ - Zolt

1

对于那些正在寻找O(n^2)答案的人，请参考以下链接：https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/ - Shirish Herwade

显示剩余3条评论

23个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- spider · Answer 1

这是我的算法：

1）将当前中心设置为第一个字母

2）同时向左和向右扩展，直到找到当前中心周围的最大回文字符串

3）如果找到的回文字符串比之前的更大，则更新它

4）将当前中心设置为下一个字母

5）对字符串中的所有字母重复步骤2）至4）

这个算法的时间复杂度为O(n)。

希望能有所帮助。

- Sazzad Hissain Khan · Answer 2

参考：Wikipedia.com

我曾经发现的最佳算法，时间复杂度为O(N)

 import java.util.Arrays;

 public class ManachersAlgorithm {

  public static String findLongestPalindrome(String s) {
    if (s==null || s.length()==0)
      return "";

    char[] s2 = addBoundaries(s.toCharArray());
    int[] p = new int[s2.length]; 
    int c = 0, r = 0; // Here the first element in s2 has been processed.
    int m = 0, n = 0; // The walking indices to compare if two elements are the same
    for (int i = 1; i<s2.length; i++) {
      if (i>r) {
        p[i] = 0; m = i-1; n = i+1;
      } else {
        int i2 = c*2-i;
        if (p[i2]<(r-i)) {
          p[i] = p[i2];
          m = -1; // This signals bypassing the while loop below. 
        } else {
          p[i] = r-i;
          n = r+1; m = i*2-n;
        }
      }
      while (m>=0 && n<s2.length && s2[m]==s2[n]) {
        p[i]++; m--; n++;
      }
      if ((i+p[i])>r) {
        c = i; r = i+p[i];
      }
    }
    int len = 0; c = 0;
    for (int i = 1; i<s2.length; i++) {
      if (len<p[i]) {
        len = p[i]; c = i;
      }
    }
    char[] ss = Arrays.copyOfRange(s2, c-len, c+len+1);
    return String.valueOf(removeBoundaries(ss));
  }

  private static char[] addBoundaries(char[] cs) {
    if (cs==null || cs.length==0)
      return "||".toCharArray();

    char[] cs2 = new char[cs.length*2+1];
    for (int i = 0; i<(cs2.length-1); i = i+2) {
      cs2[i] = '|';
      cs2[i+1] = cs[i/2];
    }
    cs2[cs2.length-1] = '|';
    return cs2;
  }

  private static char[] removeBoundaries(char[] cs) {
    if (cs==null || cs.length<3)
      return "".toCharArray();

    char[] cs2 = new char[(cs.length-1)/2];
    for (int i = 0; i<cs2.length; i++) {
      cs2[i] = cs[i*2+1];
    }
    return cs2;
  }    
}

- Tomer keisar · Answer 3

我的解决方案是：

static string GetPolyndrom(string str)
{
    string Longest = "";

    for (int i = 0; i < str.Length; i++)
    {
        if ((str.Length - 1 - i) < Longest.Length)
        {
            break;
        }
        for (int j = str.Length - 1; j > i; j--)
        {
            string str2 = str.Substring(i, j - i + 1);
            if (str2.Length > Longest.Length)
            {
                if (str2 == str2.Reverse())
                {
                    Longest = str2;
                }
            }
            else
            {
                break;
            }
        }

    }
    return Longest;
}