寻找字符串的子串，使得子串长度乘以其出现次数的积最大化。

Question

寻找字符串的子串，使得子串长度乘以其出现次数的积最大化。

5

我在思考以下问题：给定一个字符串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) 时间。我想知道是否有更有效的方法来实现这个功能。

- n00bc0d3r

出现次数可以重叠吗？例如，对于 S = 'ababa'，答案是 3 * 2 = 6 吗？ - Abhishek Bansal

是的，出现次数可以重叠。 - n00bc0d3r

4个回答

1

一个想法：您可以通过创建出现列表来缩短算法。这样，在运行countOccurences之前，您将检查是否已经为该出现次数计数，并且您不会再次运行countOccurences以进行相同的出现次数。

这是第一次优化，还应该有其他优化，但这是一个开始。

- singe3

0

改进后的算法如下：（伪代码）

int max = 0;

 for(int i=0;i<str.length;) {

   occurences = get_index(str[i]);

   for(int j=i+1;j<str.length;j++) {

      if(occurences.size()==0)
         break;

      for(int k=0;k<occurences.size();k++) {

           int next_ind = occurrences[k]+j-i;

           if(next_ind==length||str[next_ind]!=str[j]) {
               delete(occurences[k]);
           }
       }

       int score = ocurrences.size()*(j-i+1);

       if(max<score)
         score = max; 
   } 

 }

时间复杂度:-

理想情况下，子字符串的出现次数应该像 n，n/2，n/3.... 最多减少，因此算法是 n*n*(1+1/2+1/3...) = O(n^2*logn)，因为 (1+1/2+1/3...1/n) => logn。使用链接列表可以轻松地以 O(1) 删除出现次数。

- Vikram Bhat

0

假设您可以使用剩余的内容计算最大可用“分数”，从而避免检查超出某个点的子字符串。我猜它仍然不太好扩展，但它人为地减少了您的“n”值。

例如，如果您有一个长度为10的字符串，并且您在前3个字符中两次获得了一个3个字符的子字符串（即0-2、3-5），那么您可以说max = 6。在那一点上，一旦您移动到i = 4之外，您就无法得分超过6，因此您可以停止吗？

- chrisb2244

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- j_random_hacker · Accepted Answer

以下是一个线性时间算法：

在输入字符串上构建后缀树。这需要O(n)的时间和空间。
使用后序DFS遍历后缀树，通过累加其子节点的值计算每个节点的后代数量。一旦已知该数量，就将其与其字符串长度（即所有边长之和）相乘，并在必要时更新最佳总分数。这也需要O(n)的时间。

关键点是：

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

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