如果输入是 '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;
}
但是找到回文子串的有效方法是什么？
O(n)使用Manacher 算法在 中完成。主要思想是动态规划和（正如其他人已经说过的）计算给定字母中心的最大回文长度的组合。
我们真正要计算的是最长回文的半径，而不是长度。半径是简单的length/2或(length - 1)/2（对于奇数长度的回文）。
pr在计算给定位置的回文半径之后，i我们使用已经计算的半径来查找 range 内的回文。这让我们（因为回文是回文）跳过对范围的进一步计算。[i - pr ; i]radiuses[i ; i + pr]
当我们在 range中搜索时，每个位置都有四种基本情况（where is in ）：[i - pr ; i]i - kk1,2,... pr
radius = 0) at
（这也意味着 at ）i - kradius = 0i + kradiusati + k与 at 相同i - k）radiusati + k被削减以适合范围，即因为i + k + radius > i + pr我们减少radius到pr - k）i + k + radius = i + pri + k完整、详细的解释将相当长。一些代码示例呢？:)
我找到了波兰老师 Mgr Jerzy Wałaszek 对该算法的 C++ 实现。
我已经将评论翻译成英文，添加了一些其他评论并简化了一点，以便更容易抓住主要部分。
看看这里。
注意：如果在理解为什么会出现问题O(n)时，请尝试这样看：在某个位置
找到半径（我们称之为半径r）之后，我们需要向后迭代r元素，但结果是我们可以跳过r向前的元素计算。因此，迭代元素的总数保持不变。
也许您可以遍历潜在的中间字符（奇数长度回文）和字符之间的中间点（偶数长度回文）并扩展每个字符，直到您无法再进一步（下一个左右字符不匹配）。
当字符串中没有很多回文时，这将节省大量计算。在这种情况下，稀疏回文字符串的成本将是 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++;
}
}
所以，每个不同的字母已经是一个回文 - 所以你已经有 N + 1 个回文，其中 N 是不同字母的数量（加上空字符串）。您可以在单次运行中做到这一点 - O(N)。
现在，对于非平凡的回文，您可以测试字符串的每个点是否成为潜在回文的中心 - 在两个方向上增长 - 这是Valentin Ruano建议的。
该解决方案将采用 O(N^2) ，因为每个测试都是 O(N) 并且可能的“中心”数量也是 O(N) - 这center是一个字母或两个字母之间的空格，再次与 Valentin 的解决方案一样。
请注意，基于Manacher 的算法，您的问题还有 O(N) 解决方案（文章描述了“最长回文”，但算法可用于计算所有这些）
我只是想出了我自己的逻辑来帮助解决这个问题。快乐编码.. :-)
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
我建议从一个基本案例开始构建并扩展，直到你拥有所有的回文。
回文有两种类型：偶数和奇数。我还没有想出如何以同样的方式处理这两者，所以我会分解它。
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 运行时，但它应该比尝试每个子字符串更有效。最坏的情况是所有相同字母的字符串，这可能比“查找每个子字符串”计划更糟糕，但是对于大多数输入，它会删除大多数子字符串，因为一旦你意识到它不是一个中心，你就可以停止查看一个回文。
我尝试了以下代码，它在这些情况下运行良好而且它也处理单个字符
少数通过的案例：
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<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);
}
}
希望它没事
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);
}
}
试试这个。它是我自己的解决方案。
// 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();
}
代码是找到所有不同的回文子串。这是我尝试过的代码。它工作正常。
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;
}
}
输出：
可能的子串： a b b a ab bb ba abb bba abba
可能的子字符串总数为 10
总回文子串为 4
可能的回文子串：[bb, a, b, abba]
耗时 1 毫秒