找到所有作为回文的子串

Question

如果输入是'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;  
}

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

Answer 1

这可以O(n)使用Manacher算法完成.

主要思想是动态编程和(正如其他人已经说过的)计算最大长度的回文以及给定字母中心的组合.

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

在计算pr给定位置的回文半径后,i我们使用已计算的半径来找到范围内的回文.这让我们(因为回文,好吧,回文)跳过了范围的进一步计算.[i - pr ; i]radiuses[i ; i + pr]

虽然我们在搜索范围内,对于每个位置的四个基本情况(这里是):[i - pr ; i]i - kk1,2,... pr

• 没有回文(radius = 0)的 (这意味着 在,太)i - k
radius = 0i + k
• 内回文,这意味着它适合范围
  (这意味着与radiusat i + k相同i - k)
• 外回文,这意味着它不适合在范围
  (这意味着radius在i + k被削减,以适应范围,即因为i + k + radius > i + pr我们减少radius到pr - k)
• 粘性回文,这意味着 (在这种情况下,我们需要搜索可能更大的半径)i + k + radius = i + pr
i + k

完整,详细的解释会很长.一些代码示例怎么样？:)

我找到了波兰老师,mgrJerzyWałaszek的这个算法的C++实现.
我已将评论翻译成英文,添加了一些其他评论并简化了一些以便更容易理解主要部分.
看看这里.

注意:如果有问题理解为什么会这样O(n),请尝试这样:在某个位置
找到半径(让我们调用它r)后,我们需要迭代r元素,但结果我们可以跳过r元素向前计算.因此,迭代元素的总数保持不变.

Answer 2

也许你可以迭代潜在的中间字符(奇数长度的回文)和字符之间的中间点(甚至是长度的回文)并延伸每个字符直到你无法进一步(下一个左右字符不匹配).

当字符串中没有多个palidromes时,这将节省大量的计算.在这种情况下,稀疏的palidrome串的成本为O(n).

对于回文密集输入,它将是O(n ^ 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++;
      }
  }

Answer 3

因此,每个不同的字母已经是一个回文 - 所以你已经有N + 1个回文,其中N是不同字母的数量(加上空字符串).你可以在单次运行中做到 - O(N).

现在,对于非平凡的回文,你可以测试你的弦的每个点是潜在回文的中心 - 在两个方向上生长 - 这是Valentin Ruano建议的.
该解决方案将采用O(N ^ 2),因为每个测试是O(N)并且可能的"中心"的数量也是O(N) - center两个字母之间的字母或空格,再次如Valentin的解决方案中那样.

注意,基于Manacher的算法,你的问题也有O(N)解决方案(文章描述了"最长的回文",但算法可以用来统计所有这些)

Answer 4

我想出了自己的逻辑,这有助于解决这个问题.快乐的编码.. :-)

System.out.println("Finding all palindromes in a given string : ");
        subPal("abcacbbbca");

private static void subPal(String str) {
        String s1 = "";
        int N = str.length(), count = 0;
        Set<String> palindromeArray = new HashSet<String>();
        System.out.println("Given string : " + str);
        System.out.println("******** Ignoring single character as substring palindrome");
        for (int i = 2; i <= N; i++) {
            for (int j = 0; j <= N; j++) {
                int k = i + j - 1;
                if (k >= N)
                    continue;
                s1 = str.substring(j, i + j);
                if (s1.equals(new StringBuilder(s1).reverse().toString())) {
                    palindromeArray.add(s1);
                }
            }

        }
        System.out.println(palindromeArray);
        for (String s : palindromeArray)
            System.out.println(s + " - is a palindrome string.");
        System.out.println("The no.of substring that are palindrome : "
                + palindromeArray.size());
    }

Output:-
Finding all palindromes in a given string : 
Given string : abcacbbbca
******** Ignoring single character as substring palindrome ********
[cac, acbbbca, cbbbc, bb, bcacb, bbb]
cac - is a palindrome string.
acbbbca - is a palindrome string.
cbbbc - is a palindrome string.
bb - is a palindrome string.
bcacb - is a palindrome string.
bbb - is a palindrome string.
The no.of substring that are palindrome : 6