logo标签列表

在一个字符串中计算回文数量

javastringalgorithmpalindrome
4

我想找出所有可能使用给定字符串的子串形成的回文字符串。

Example: input = abbcbbd.
Possible palindromes are a,b,b,c,b,b,d,bb,bcb, bbcbb,bb

这是我实现的逻辑：

public int palindromeCount(String input) {
    int size = input.length();// all single characters in string are treated as palindromes.
    int count = size;
    for(int i=0; i<size; i++) {
        for(int j=i+2; j<=size; j++) {
            String value = input.substring(i, j);
            String reverse = new StringBuilder(value).reverse().toString();
            if(value.equals(reverse)) {
                count++;
            }
        }
    }
    return count;
}

这里的时间复杂度较高，我该如何改进此逻辑的性能？

@Code-Apprentice，是的，我错过了它，现在已经包括进去了。 - learner
@Code-Apprentice，当我在编程考试中使用它时，它会因性能错误而失败，显示超时，但它没有提供样例数据来验证我的代码。 - learner
1
你确定要像你的例子一样让相同的回文出现多次吗？我期望abbcbbd会产生a，b，c，d，bb，bab，bbb，bcb，bdb，bbbb，bbabb，bbcbb，bbdbb。 - Dave
@learner 你想多次计算相同的子字符串吗？例如，你想将所有4个b都计算为四个不同的回文吗？ - Code-Apprentice
@Code-Apprentice，是的，我想要分别计算它们。 - learner
显示剩余8条评论
2个回答
7
如果您熟悉一些重量级数据结构，那么可以在O(n)的时间内完成这个问题，不过我承认编写代码并不容易。 :-)
我们需要两个工具来解决这个问题。
第一个工具：广义后缀树。广义后缀树是一种数据结构，直观地说，它是一个包含两个字符串S和T的所有后缀的Trie树，但以一种更节省空间的方式表示。
第二个工具：最近公共祖先查询。最近公共祖先查询结构（或LCA查询）是围绕特定树构建的一种数据结构。它被设计为有效地回答形式为“给定树中的两个节点，它们的最低公共祖先是什么？”的查询。
重要的是，对于长度为m的两个字符串，广义后缀树可以在O(m)时间内构建，并且可以在O(m)时间内构建LCA查询，使所有查询的时间为O(1)。这些并不是显而易见的运行时间；当它们首次被发现时，所需的算法和数据结构是可出版的结果。
假设我们拥有这两个结构，我们可以构建第三个数据结构，这就是我们将用来得到最终算法的：
第三个工具：最长公共扩展查询。最长公共扩展查询数据结构（或LCE查询）是围绕两个字符串S和T构建的一种数据结构。它支持以下形式的查询：给定一个索引i到字符串S和一个索引j到字符串T，从索引i在S中和索引j在T中开始出现的最长字符串的长度是多少？
以这两个字符串为例：
S: OFFENSE
   0123456

T: NONSENSE
   01234567

如果从字符串S的索引3和字符串T的索引4开始进行LCE查询，答案将是字符串ENSE。另一方面，如果我们从字符串S的索引4和字符串T的索引0开始进行LCE查询，我们将得到字符串N。
更严格地说，LCE查询结构实际上并没有返回您在两个位置找到的实际字符串，而是返回它的长度。
可以在O(m)时间内建立一个针对长度为m的字符串S和T的LCE数据结构，以便每个查询需要O(1)的时间。实现此目标的技术涉及构建两个字符串的广义后缀树，然后在其上构建LCA数据结构。关键的洞见是，在后缀树中，字符串S的后缀i和字符串T的后缀j的LCE是它们的最低公共祖先(LCA)。
LCE结构对于解决此问题非常有用。为了说明这一点，让我们看一下示例字符串abbcbbd。现在，考虑该字符串及其反向字符串，如下所示:
 S: abbcbbd
    0123456

 T: dbbcbba
    0123456

一个字符串中的回文串可以分为两种形式。第一种是奇数长度的回文串，这样的回文串有一个中心字符c和从中心向前向后延伸的“半径”。例如，字符串bbcbb是一个以字符c为中心，半径为bb的奇数长度回文串。

我们可以通过使用LCE查询来计算一个字符串中有多少个奇数长度的回文串。具体来说，需要在该字符串和其反转后的字符串上建立LCE查询结构。然后，对于原始字符串中的每个位置，在原始字符串中查询该位置与镜像字符串对应位置的LCE值。这将给出以该点为中心的最长奇数长度的回文串（更具体地说，它会给出半径的长度加1，因为这两个位置上的字符总是匹配的）。一旦我们知道了在字符串中以该位置为中心的最长奇数长度的回文串，我们就可以计算以该位置为中心的奇数长度回文串的数量：这将等于将更长的回文串切割掉前后字符所得到的所有短回文串的数量。

有了这个思路，我们可以如下计算一个字符串中所有奇数长度回文串的数量：

for i from 0 to length(S) - 1:
    total += LCE(i, length(S) - 1 - i)

另一类回文是偶数长度的回文，它们没有中心，而是由两个相等的半径组成。我们可以使用LCE查询来查找它们，但不是查看某个位置i和其在反转字符串中对应的位置，而是查看原始字符串中的位置i和在反转字符串中对应于索引i-1的位置。这样可以实现：
for i from 1 to length(S) - 1:
    total += LCE(i, length(S) - i)

总的来说，这个解决方案

  • 从原始字符串和反转字符串构建了一个LCE查询结构。反转字符串需要O(m)时间，建立LCE查询结构需要O(m)时间。此步骤的总时间为O(m)。
  • 对LCE结构进行2m-1次查询。每次查询需要O(1)时间。此步骤的总时间为O(m)。

我相当确定可以在不使用如此沉重的工具的情况下实现这个运行时，但至少说明了存在一种线性时间的解决方案。

希望这能有所帮助！

7
以下是针对该算法进行优化时需要考虑的一些事项：
1. 什么是回文？回文是一个对称的字符串，这意味着它必须有一个中心支点！中心支点可以是以下之一：
  • 一个字母，比如说 "aba" 中的字母 "b"，或者
  • 两个字母之间的位置，比如说 "aa" 中两个字母之间的位置。
因此，总共有2n - 1个可能的支点。
2. 然后，您可以从每个支点向外搜索。以下是一个示例：
  • 样本字符串："abcba"
  • 首先，在 "c" 上取一个支点：
    • abcba → c 是一个回文，然后在每一侧扩大搜索范围 1。
    • abcba → bcb 是一个回文，然后在每一侧扩大搜索范围 1。
    • abcba → abcba 是一个回文，所以我们知道字符串中至少有 3 个回文。
  • 继续使用所有支点。
通过这种方法，运行时间复杂度为 O(n2)。
你如何确定复杂度为O(n^2)？你能详细解释一下这个分析吗？此外，OP的解决方案是O(n^2)吗？我看到了嵌套的for循环，但在substring()和reverse()中还有一些额外的循环，如果我的计算正确的话，那么他的解决方案将是O(n^3)。 - Code-Apprentice
是的，我认为OP的答案是n^3，因为它使用了最坏情况下为n的reverse。我的答案是n^2，因为每个枢轴的运行时间最多为n/2，有2n-1个枢轴。 - EDToaster
1
@Code-Apprentice：正如你所说，OP的解决方案确实是O(n³)。而这个答案中的解决方案是O(n²)，因为在给定枢轴点的情况下，寻找长度为m的回文只需要O(1)的时间，这是可能的，因为它使用了在同一枢轴点上寻找长度为m-2的回文的结果。 - ruakh
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接