我有一个蛮力解决方案来在 O(n^2) 时间内计算输入字符串中的所有子字符串。当我的输入字符串很长时,它需要很长时间。

我们如何在 O(n) 时间内找到所有可能的子串?

我只是在寻找所有子字符串的计数,其中子字符串中的第一个和最后一个字符是相同的。正如您所看到的,我只在下面的代码中从函数返回计数。我想在 O(n) 时间内完成

我的蛮力解决方案:

// I am calculating count of all substrings where first and last substring character are equal

public class Solution {

public static void main(String[] args) {

    String inputString = "ababaca";

    System.out.println(findSubstringByBruteForcce(inputString, inputString.length()));

}

private static long findSubstringByBruteForcce(String inputString, int length) {
    long count = 0;
    for (int i = 0; i < length; i++) {
        for (int j = 1; j <= length - i; j++) {
            String str = inputString.substring(i, i + j);
            if(str.length() == 1){
                count = count + 1;
            }else {
                if(str.substring(0, 1).equals(str.substring(str.length() - 1, str.length()))){
                    count = count + 1;
                }
            }
        }
    }
    return count;
}

}

如何优化上述解决方案并在 O(N) 时间内找到答案?输入字符串可能非常大(大约 10^6 长度)并且蛮力运行大约需要 20 秒。我希望最大运行时间低于 2 秒。

最佳答案

由于子串身份由边界索引而不是内容决定,因此计算每个字母的频率就足够了,然后对于每个字母,将项 (频率 + 1) * 频率 div 2 相加,因为每对字母位置与重复但不考虑顺序会产生一个计数的子串。

关于java - 是否有一种技巧/算法可以让我们在 O(n) 时间内找到所有可能的子串,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/30960667/

10-16 19:30
查看更多