Java 找出所有回文的子串

Find all substrings that are palindromes

提问by Himanshu Yadav

If the input is 'abba' then the possible palindromes are a, b, b, a, bb, abba.
I understand that determining if string is palindrome is easy. It would be like:

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

But what is the efficient way of finding palindrome substrings?

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

采纳答案by Micha? Rybak

This can be done in O(n), using Manacher's algorithm.

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

The main idea is a combination of dynamic programming and (as others have said already) computing maximum length of palindrome with center in a given letter.

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

---

---

What we really want to calculate is radiusof the longest palindrome, not the length. The radiusis simply length/2or (length - 1)/2(for odd-length palindromes).

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

After computing palindrome radius prat given position iwe use already computed radiusesto find palindromes in range [i - pr ; i]. This lets us (because palindromes are, well, palindromes) skip further computation of radiusesfor range [i ; i + pr].

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

While we search in range [i - pr ; i], there are four basic cases for each position i - k(where kis in 1,2,... pr):

当我们在 range 中搜索时，每个位置都有四种基本情况（在中的位置）：[i - pr ; i]i - kk1,2,... pr

• no palindrome (radius = 0) at i - k
  (this means radius = 0at i + k, too)
• innerpalindrome, which means it fits in range
  (this means radiusat i + kis the same as at i - k)
• outerpalindrome, which means it doesn't fit in range
  (this means radiusat i + kis cut downto fit in range, i.e because i + k + radius > i + prwe reduce radiusto pr - k)
• stickypalindrome, which means i + k + radius = i + pr
  (in that case we need to search for potentially bigger radius at i + k)

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

Full, detailed explanation would be rather long. What about some code samples? :)

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

I've found C++ implementation of this algorithm by Polish teacher, mgr Jerzy Wa?aszek.
I've translated comments to english, added some other comments and simplified it a bit to be easier to catch the main part.
Take a look here.

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

---

---

Note:in case of problems understanding why this is O(n), try to look this way:
after finding radius(let's call it r) at some position, we need to iterate over relements back, but as a result we can skip computation for relements forward. Therefore, total number of iterated elements stays the same.

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

回答by Valentin Ruano

Perhaps you could iterate across potential middle character (odd length palindromes) and middle points between characters (even length palindromes) and extend each until you cannot get any further (next left and right characters don't match).

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

That would save a lot of computation when there are no many palidromes in the string. In such case the cost would be O(n) for sparse palidrome strings.

当字符串中没有很多回文时，这将节省大量计算。在这种情况下，稀疏回文字符串的成本将为 O(n)。

For palindrome dense inputs it would be O(n^2) as each position cannot be extended more than the length of the array / 2. Obviously this is even less towards the ends of the array.

对于回文密集输入，它将是 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++;
      }
  }

回答by Eric Barr

I suggest building up from a base case and expanding until you have all of the palindomes.

我建议从一个基本案例开始构建并扩展，直到你拥有所有的回文。

There are two types of palindromes: even numbered and odd-numbered. I haven't figured out how to handle both in the same way so I'll break it up.

有两种类型的回文：偶数和奇数。我还没有想出如何以相同的方式处理这两者，所以我将其分解。

1) Add all single letters

1) 添加所有单个字母

2) With this list you have all of the starting points for your palindromes. Run each both of these for each index in the string (or 1 -> length-1 because you need at least 2 length):

2) 有了这个列表，你就有了回文的所有起点。为字符串中的每个索引运行这两个（或 1 -> length-1，因为您至少需要 2 个长度）：

findAllEvenFrom(int index){
  int i=0;
  while(true) {
    //check if index-i and index+i+1 is within string bounds

    if(str.charAt(index-i) != str.charAt(index+i+1)) 
      return; // Here we found out that this index isn't a center for palindromes of >=i size, so we can give up

    outputList.add(str.substring(index-i, index+i+1));
    i++;
  }
}
//Odd looks about the same, but with a change in the bounds.
findAllOddFrom(int index){
  int i=0;
  while(true) {
    //check if index-i and index+i+1 is within string bounds

    if(str.charAt(index-i-1) != str.charAt(index+i+1)) 
      return;

    outputList.add(str.substring(index-i-1, index+i+1));
    i++;
  }
}

I'm not sure if this helps the Big-O for your runtime, but it should be much more efficient than trying each substring. Worst case would be a string of all the same letter which may be worse than the "find every substring" plan, but with most inputs it will cut out most substrings because you can stop looking at one once you realize it's not the center of a palindrome.

我不确定这是否有助于您的运行时的 Big-O，但它应该比尝试每个子字符串更有效。最坏的情况是所有相同字母的字符串，这可能比“查找每个子字符串”计划更糟糕，但是对于大多数输入，它会删除大多数子字符串，因为一旦您意识到它不是一个字符串的中心，您就可以停止查看它回文。

回答by kiruwka

So, each distinct letter is already a palindrome - so you already have N + 1 palindromes, where N is the number of distinct letters (plus empty string). You can do that in single run - O(N).

所以，每个不同的字母已经是一个回文 - 所以你已经有 N + 1 个回文，其中 N 是不同字母的数量（加上空字符串）。您可以在单次运行中做到这一点 - O(N)。

Now, for non-trivial palindromes, you can test each point of your string to be a center of potential palindrome - grow in both directions - something that Valentin Ruanosuggested.
This solution will take O(N^2) since each test is O(N) and number of possible "centers" is also O(N) - the centeris either a letter or space between two letters, again as in Valentin's solution.

现在，对于非平凡回文，您可以测试字符串的每个点是否成为潜在回文的中心 - 双向增长 - 这是Valentin Ruano建议的。
这个解决方案将需要 O(N^2) 因为每个测试都是 O(N) 并且可能的“中心”的数量也是 O(N) -center是两个字母之间的一个字母或空格，同样在 Valentin 的解决方案中。

Note, there is also O(N) solution to your problem, based on Manacher'salgoritm (article describes "longest palindrome", but algorithm could be used to count all of them)

请注意，您的问题也有 O(N) 解决方案，基于Manacher 的算法（文章描述了“最长回文”，但算法可用于计算所有这些）

回答by Bala

I just came up with my own logic which helps to solve this problem. Happy coding.. :-)

我只是想出了我自己的逻辑来帮助解决这个问题。快乐编码.. :-)

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

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

回答by user5999909

    // Maintain an Set of palindromes so that we get distinct elements at the end
    // Add each char to set. Also treat that char as middle point and traverse through string to check equality of left and right char


static int palindrome(String str) {

    Set<String> distinctPln = new HashSet<String>();
    for (int i=0; i<str.length();i++) {
        distinctPln.add(String.valueOf(str.charAt(i)));
        for (int j=i-1, k=i+1; j>=0 && k<str.length(); j--, k++) {
            // String of lenght 2 as palindrome
            if ( (new Character(str.charAt(i))).equals(new Character(str.charAt(j)))) { 
                distinctPln.add(str.substring(j,i+1));
            }
            // String of lenght 2 as palindrome
            if ( (new Character(str.charAt(i))).equals(new Character(str.charAt(k)))) { 
                distinctPln.add(str.substring(i,k+1));
            }
            if ( (new Character(str.charAt(j))).equals(new Character(str.charAt(k)))) { 
                distinctPln.add(str.substring(j,k+1));
            } else {
                continue;
            }
        }
    }

    Iterator<String> distinctPlnItr = distinctPln.iterator();
    while ( distinctPlnItr.hasNext()) {
        System.out.print(distinctPlnItr.next()+ ",");
    }
    return distinctPln.size();

}

回答by hemantvsn

I tried the following code and its working well for the cases Also it handles individual characters too

我尝试了以下代码并且它在这些情况下运行良好而且它也处理单个字符

Few of the cases which passed:

通过的案例很少：

abaaa --> [aba, aaa, b, a, aa] 
geek  --> [g, e, ee, k] 
abbaca --> [b, c, a, abba, bb, aca] 
abaaba -->[aba, b, abaaba, a, baab, aa] 
abababa -->[aba, babab, b, a, ababa, abababa, bab] 
forgeeksskeegfor --> [f, g, e, ee, s, r, eksske, geeksskeeg, 
                      o, eeksskee, ss, k, kssk]

Code

代码

static Set<String> set = new HashSet<String>(); 
static String DIV = "|";

public static void main(String[] args) {
    String str = "abababa";
    String ext = getExtendedString(str);

    // will check for even length palindromes
    for(int i=2; i<ext.length()-1; i+=2) {
        addPalindromes(i, 1, ext);
    }
    // will check for odd length palindromes including individual characters
    for(int i=1; i<=ext.length()-2; i+=2) {
        addPalindromes(i, 0, ext);
    }
    System.out.println(set);
}

/*
 * Generates extended string, with dividors applied
 * eg: input = abca
 * output = |a|b|c|a|
 */
static String getExtendedString(String str) {
    StringBuilder builder = new StringBuilder();
    builder.append(DIV);
    for(int i=0; i< str.length(); i++) {
        builder.append(str.charAt(i));
        builder.append(DIV);

    }
    String ext = builder.toString();
    return ext;
}

/*
 * Recursive matcher
 * If match is found for palindrome ie char[mid-offset] = char[mid+ offset]
 * Calculate further with offset+=2
 * 
 * 
 */
static void addPalindromes(int mid, int offset, String ext) {
    // boundary checks
    if(mid - offset <0 || mid + offset > ext.length()-1) {
        return;
    }
    if (ext.charAt(mid-offset) == ext.charAt(mid+offset)) {
        set.add(ext.substring(mid-offset, mid+offset+1).replace(DIV, ""));
        addPalindromes(mid, offset+2, ext);
    }
}

Hope its fine

希望没事

回答by user8778562

Code is to find all distinct substrings which are palindrome. Here is the code I tried. It is working fine.

代码是找到所有不同的回文子串。这是我试过的代码。它工作正常。

import java.util.HashSet;
import java.util.Set;

public class SubstringPalindrome {

    public static void main(String[] args) {
        String s = "abba";
        checkPalindrome(s);
}

public static int checkPalindrome(String s) {
    int L = s.length();
    int counter =0;
    long startTime = System.currentTimeMillis();
    Set<String> hs = new HashSet<String>();
    // add elements to the hash set
    System.out.println("Possible substrings: ");
    for (int i = 0; i < L; ++i) {
      for (int j = 0; j < (L - i); ++j) {
          String subs = s.substring(j, i + j + 1);
            counter++;
            System.out.println(subs);
            if(isPalindrome(subs))
                hs.add(subs);
      }
    }
    System.out.println("Total possible substrings are "+counter);
    System.out.println("Total palindromic substrings are "+hs.size());
    System.out.println("Possible palindromic substrings: "+hs.toString());
    long endTime = System.currentTimeMillis();
    System.out.println("It took " + (endTime - startTime) + " milliseconds");
    return hs.size();
}
public static boolean isPalindrome(String s) {
    if(s.length() == 0 || s.length() ==1)
        return true;
    if(s.charAt(0) ==  s.charAt(s.length()-1))
        return isPalindrome(s.substring(1, s.length()-1));
    return false;
}

}

}

OUTPUT:

输出：

Possible substrings: a b b a ab bb ba abb bba abba

可能的子串： a b b a a b bb ba abb bba abba

Total possible substrings are 10

可能的子串总数为 10

Total palindromic substrings are 4

回文子串总数为 4

Possible palindromic substrings: [bb, a, b, abba]

可能的回文子串：[bb, a, b, abba]

It took 1 milliseconds

花了 1 毫秒

回答by Bhavani

public class PolindromeMyLogic {

static int polindromeCount = 0;

private static HashMap<Character, List<Integer>> findCharAndOccurance(
        char[] charArray) {
    HashMap<Character, List<Integer>> map = new HashMap<Character, List<Integer>>();
    for (int i = 0; i < charArray.length; i++) {
        char c = charArray[i];
        if (map.containsKey(c)) {
            List list = map.get(c);
            list.add(i);
        } else {
            List list = new ArrayList<Integer>();
            list.add(i);
            map.put(c, list);
        }
    }
    return map;
}

private static void countPolindromeByPositions(char[] charArray,
        HashMap<Character, List<Integer>> map) {
    map.forEach((character, list) -> {
        int n = list.size();
        if (n > 1) {
            for (int i = 0; i < n - 1; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (list.get(i) + 1 == list.get(j)
                            || list.get(i) + 2 == list.get(j)) {
                        polindromeCount++;
                    } else {
                        char[] temp = new char[(list.get(j) - list.get(i))
                                + 1];
                        int jj = 0;
                        for (int ii = list.get(i); ii <= list
                                .get(j); ii++) {
                            temp[jj] = charArray[ii];
                            jj++;
                        }
                        if (isPolindrome(temp))
                            polindromeCount++;
                    }

                }
            }
        }
    });
}

private static boolean isPolindrome(char[] charArray) {
    int n = charArray.length;
    char[] temp = new char[n];
    int j = 0;
    for (int i = (n - 1); i >= 0; i--) {
        temp[j] = charArray[i];
        j++;
    }
    if (Arrays.equals(charArray, temp))
        return true;
    else
        return false;
}

public static void main(String[] args) {
    String str = "MADAM";
    char[] charArray = str.toCharArray();
    countPolindromeByPositions(charArray, findCharAndOccurance(charArray));
    System.out.println(polindromeCount);
}
}

Try out this. Its my own solution.

试试这个。它是我自己的解决方案。