查找字符串中的所有Palindrome

Question

可能重复： Algorithm to find palindromes

如何在字符串中找到所有回文，如：

AA BB AA TTT AA BB

我知道如何在一个字符串中找到回文，如果我通过删除“”字符来合并这些字符串，我仍然可以找到palindromes...but，如果这样做，我如何重建原始单词.

或者是否还有其他方法可以减少time...Any线索..？

Answer 1

编辑:我假设您要问的是:给定一串字符，我如何确定所有可能的子字符串是回文？

您可以从单个字符(它们本身是微不足道的回文)构建，然后考虑长度为2的所有子字符串，然后考虑长度为3的所有子字符串。

幸运的是，palindome具有递归关系，因此如果删除第一个和最后一个字母，还必须有回文。因此，如果长度为4的字符串是回文(如ABBA)，那么删除第一个和最后一个字符('BB')的子字符串也必须是回文。

考虑一个动态规划解决方案来计算任意给定的字符串，因为上面定义的递归关系满足DP的最优子问题要求。

Answer 2

这个问题实际上可以归结为查找所有子字符串。在遍历了字符串中的每个“单词”( AA、BB、AA、TTT等)之后，您可以将每个单词看作单个字符，因此映射AA->a、BB->b、TTT->t等，现在从您的示例中可以看到新的“缩减”字符串是abatab。查找abatab的所有子字符串，并检查每个子字符串是否为回文，如果是，则可以通过查找映射中的单词打印出原始字符串。aba -> AABBAA就是一个例子。

如果你的单词不是由相同的字母组成的话，这个问题就会变得更有趣。如果你有AB BA。在本例中，AB和BA不是回文，但它们的连接是ABBA。

Answer 3

SauceMaster's answer描述了如何解决回文问题。

我只想回答这个问题。

我知道如何在一个字符串中找到回文，如果我通过删除“”字符来合并这些字符串，我仍然可以找到palindromes...but，如果这样做，我如何重建原始单词？

先复制字符串。