查找是回文所有子 [英] Find all substrings that are palindromes

问题描述

如果输入的是'阿爸'，那么可能的回文是A，B，B，A，BB，ABBA。
据我所知，确定是否字符串是回文容易。这将是这样的：

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:

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?

推荐答案

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

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

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

我们真的要计算的最长回文，而不是长度的它的半径的是什么。 在半径的仅仅是长/ 2 或（长度 - 1）/ 2 （对奇数长度回文）。

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

在计算回文半径的 新闻 的，在给定位置的 我 我们使用已计算出的半径的寻找范围内的回文 [的 我 - PR;我 的] 。这让我们（因为palindroms是，嗯，palindroms）跳过半径的范围 [的 我;我+ PR 的] 。

After computing palindrome radius pr at given position i we use already computed radiuses to find palindromes in range [i - pr ; i]. This lets us (because palindroms are, well, palindroms) skip futher computation of radiuses for range [i ; i + pr].

虽然我们在范围内搜索 [的 我 - PR;我 的] ，有四种基本情况下为每个位置的 我 - K 的（其中的 K 的是 1,2，...公关 的）：

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

• 在没有回文（ 半径= 0 的）在 我 - K 的
  （此方法的 半径= 0 的的的 I + K 的，太）
• 的内的回文，这意味着它的范围
  适合 （此方法的 半径 的的的 I + K 的是同在的 我 - K 的）
• 的外的回文，这意味着它不适合的范围内
  （此方法的 半径 的的的 I + K 的是削减的以适应范围，即因为 I + K +半径大于1 + PR 的我们减少的 半径 的到的 公关 - K 的）
• 的粘稠的回文，这意味着的 I + K +半径= I + PR 的
  （在这种情况下，我们需要寻找潜在的更大半径的 I + K 的）

• no palindrome (radius = 0) at i - k
  (this means radius = 0 at i + k, too)
• inner palindrome, which means it fits in range
  (this means radius at i + k is the same as at i - k)
• outer palindrome, which means it doesn't fit in range
  (this means radius at i + k is cut down to fit in range, i.e because i + k + radius > i + pr we reduce radius to pr - k)
• sticky palindrome, which means i + k + radius = i + pr
  (in that case we need to search for potentially bigger radius at i + k)

完整，详细的解释将是相当长的。来点code样？ ：）

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

我发现C ++实现这个算法由波兰的老师，主教耶Wałaszek。
我翻译注释为英语，增加了一些其他意见，并简化了一点更容易捕捉的主要部分。
看看这里。

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.

注意：的情况下理解为什么这是 O（N）的问题，尝试一下这种方法：
发现后的半径的（姑且称之为的 研究 的），在某个位置，我们需要遍历的 <$ 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 r elements back, but as a result we can skip computation for r elements forward. Therefore, total number of iterated elements stays the same.

这篇关于查找是回文所有子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！