找到所有作为回文的子串

如果输入是“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

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

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

---

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

在给定位置i计算回文半径pr ，我们使用已计算的半径来找到范围内的回文[ i - pr ; i i - pr ; i ] 。 这让我们（因为回文是好的，回文）会跳过范围[ i ; i + pr i ; i + pr ] 。

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

• 在i - k没有回文（ radius = 0 ）
  （这意味着在i + k radius = 0 ）
• 内回文，这意味着它适合范围
  （这意味着i + k处的radius与i - k处的radius相同）
• 外回文，这意味着它不适合范围
  （这意味着i + k处的radius 减小到适合范围，即因为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），因为每个位置不能延伸超过arrays/ 2的长度。显然，这更靠近arrays的末端。

  public Set palindromes(final String input) { final Set 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 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 palindromeArray = new HashSet(); 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 

Answer 5

我建议从一个基础案例建立并扩展，直到你拥有所有的palindomes。

有两种类型的回文：偶数和奇数。 我还没弄明白如何以同样的方式处理两者，所以我会分手。

1）添加所有单个字母

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++; } } 

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

Answer 6

  // 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 distinctPln = new HashSet(); for (int i=0; i=0 && k distinctPlnItr = distinctPln.iterator(); while ( distinctPlnItr.hasNext()) { System.out.print(distinctPlnItr.next()+ ","); } return distinctPln.size(); } 

Answer 7

我尝试了以下代码，它适用于案例也适用于个别字符

通过的案件很少：

 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] 

码

 static Set set = new HashSet(); 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) { 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); } } 

希望它好

Answer 8

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

 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 hs = new HashSet(); // 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：

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

可能的子串总数为10

总回文子串是4

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

花了1毫秒