有没有一个技巧/算法,通过它我们可以在O(n)时间内找到所有可能的子串

Question

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

我们怎样才能在O(n)时间内找到所有可能的子串？

我只查找子字符串中第一个和最后一个字符相同的所有子字符串的计数.正如您所看到的,我只在下面的代码中从函数返回count.我想在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秒.

Answer 1

由于子串标识由边界索引而不是内容确定,因此计算每个字母的频率就足够了,然后,对于每个字母,将术语(频率+ 1)*频率div 2相加,因为每对字母位置都是重复,但不考虑订单产生计数的子字符串.