查找属于回文的所有子字符串

一尘不染

查找属于回文的所有子字符串

algorithm

如果输入为“ 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;  
}

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

阅读 298

2020-07-28

共1个答案

一尘不染

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

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

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

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

在range内搜索时，每个位置（在中）都有四种基本情况：[ i - pr ; i] i - k k 1,2,... pr

在上也没有回文（ radius = 0 ）（也表示在） i - k
radius = 0 i + k
内回文，它在适合范围，其装置
（此装置 radius 以 i + k 相同于 i - k ）
外回文，这意味着它不适合在范围
（这意味着 radius 在 i + k 被削减到配合在范围，即因为 i + k + radius> i + pr_我们减少
radius 到 pr - k_ ）
粘性回文，这意味着（在这种情况下，我们需要在处搜索可能更大的半径） i + k + radius = i + pr
i + k

完整，详细的解释将相当长。那一些代码样本呢？:)

我发现波兰老师mgr JerzyWałaszek对此算法进行了C ++实现。
我已将评论翻译为英语，添加了一些其他评论，并对其进行了简化，以使其更容易理解主要部分。
在这里看看。

注意： 万一遇到问题O(n)，请尝试这样查找：在某个位置
找到半径（我们称之为 r ）后，我们需要将 r 元素迭代回去，但是结果是我们可以跳过对 r
元素的计算。因此，迭代元素的总数保持不变。

2020-07-28