查找所有回文子字符串

substring algorithm java palindrome

2022-09-02 00:10:56

如果输入是“abba”，那么可能的回文是a，b，b，a，bb，abba。
我知道确定字符串是否为回文很容易。它就像这样：

public static boolean isPalindrome(String str) {
 int len = str.length();
 for(int i=0; i<len/2; i++) {
     if(str.charAt(i)!=str.charAt(len-i-1) {
         return false;
     }
 return true;  
}

但是，找到回文子字符串的有效方法是什么？

答案 1

这可以在中使用 Manacher 算法在中完成。`O(n)`

主要思想是动态规划和（正如其他人已经说过的）计算给定字母中中心回文的最大长度的组合。

我们真正想要计算的是最长回文的半径，而不是长度。半径为简单或（对于奇数长度回文）。length/2(length - 1)/2

在给定位置 i 处计算回文半径 pr 之后，我们使用已经计算的半径来查找 i - pr ; i 范围内的回文。这让我们（因为回文是回文）跳过范围i ; i + pr的进一步计算。[]radiuses[]

当我们在范围 i - pr ; i 中搜索时，每个位置 i - k 有四种基本情况（其中 k 在 1，2 中,...pr）：[]

在 i - k
处没有回文（半径 = 0）（这意味着在 i + k 处半径 = 0）
内回文，这意味着它适合范围
（这意味着i + k处的半径与i - k处的半径相同）)
外回文，这意味着它不适合范围
（这意味着i + k处的半径被削减以适合范围，即因为i + k + 半径>i + pr，我们将半径减小为pr - k)
粘性回文，这意味着 i + k + 半径 = i + pr
（在这种情况下，我们需要在 i + k 处搜索可能更大的半径)

完整、详细的解释会相当长。一些代码示例呢？:)

我发现波兰老师耶日·瓦瓦谢克（Jerzy Wałaszek）C++实现了这个算法。
我已将评论翻译成英语，添加了一些其他评论，并对其进行了一些简化，以便于捕获主要部分。
请看这里。

注意：如果理解为什么会这样，请尝试这样看：
在某个位置找到半径（我们称之为r）后，我们需要迭代r元素，但结果是我们可以向前跳过r元素的计算。因此，迭代元素的总数保持不变。O(n)

答案 2

也许您可以迭代潜在的中间字符（奇数长度回文）和字符之间的中间点（偶数长度回文），并扩展每个字符，直到您无法进一步获取（下一个左字符和右字符不匹配）。

当字符串中没有很多palidromes时，这将节省大量计算。在这种情况下，稀疏的palidrome字符串的成本将是O（n）。

对于回文密集输入，它将是 O（n^2），因为每个位置的扩展不能超过数组 / 2 的长度。显然，这甚至更少接近数组的末端。

  public Set<String> palindromes(final String input) {

     final Set<String> result = new HashSet<>();

     for (int i = 0; i < input.length(); i++) {
         // expanding even length palindromes:
         expandPalindromes(result,input,i,i+1);
         // expanding odd length palindromes:
         expandPalindromes(result,input,i,i);
     } 
     return result;
  }

  public void expandPalindromes(final Set<String> result, final String s, int i, int j) {
      while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
            result.add(s.substring(i,j+1));
            i--; j++;
      }
  }

查找所有回文子字符串

这可以在 中使用 Manacher 算法在 中完成。O(n)

这可以在中使用 Manacher 算法在中完成。`O(n)`