查找字符串的子字符串,以使子字符串长度与其出现次数的乘积最大化

Question

我在考虑以下问题:给定一个字符串S,让第i ^个子字符串的长度为l _i,第i ^个子字符串的出现次数为o _i.打印子字符串,使l _i*o _i最大化.

我有这个问题的O(n ³)解决方案(蛮力),我生成所有子串并找到具有最大值的子串.我的代码如下:

public static void solve(String S) {
    long max = Integer.MIN_VALUE;
    String res = "";
    for (int i = 0; i < S.length(); i++) {
        for (int j = 1; j <= S.length() - i; j++) {
            String s = S.substring(i, i + j);
            int o = countOccurrences(S, s);
            long p = (long) o * (long) s.length();
            if (max < p) {
                max = p;
                res = s;
            }
        }
    }
    System.out.println(res);
}

其中countOccurrences()方法需要O(n)时间.我想知道是否有更有效的方法来实现这一目标.

Answer 1

这是一个线性时间算法：

1. 在输入字符串上构建后缀树。这需要 O(n) 时间和空间。
2. 遍历后序 DFS 中的后缀树，通过将其子节点的值相加来计算每个节点的后代数量。一旦知道节点的这个数量，就将其乘以它的字符串长度（它是从根开始的所有边的长度之和），并在必要时更新迄今为止的最佳总数。这也需要 O(n) 时间。

关键点是

• 后缀树仅包含线性数量的内部节点，并且
• 任何不对应于内部节点的子串都不能产生最大分数。 这是因为，当您从后缀树根追踪它时，它必须到达某个边缘的“中途向下”——但您始终可以进一步扩展它，而不会减少出现次数（即后代的数量），从而提高分数，继续向下到下一个节点。

也可以使用后缀数组而不是后缀树来完成此操作，在这种情况下，可能需要一个常数因子更少的内存，但会为运行时间添加一个对数因子。