计算字符串的所有子字符串并检查给定条件的最快方法

Question

计算给定字符串的所有可能子字符串并检查它们是否满足以下条件的最快方法是什么？

的条件是： 如果第一和所生成的字符串的最后一个字符是相同的，然后计数被递增一。我们需要找到给定非常大的字符串的所有可能的子字符串。

我已经试过天真蛮力方法，但是它并没有与长度10^7字符串的工作。 请帮助:(

for(int c = 0 ; c < length ; c++) 
     { 
      for(i = 3 ; i <= length - c ; i++) 
      { 
       String sub = str.substring(c, c+i); 
       System.out.println(sub); 
       if(sub.charAt(0) == sub.charAt(sub.length()-1)){ 
        count++; 
       } 
      } 
     } 

Answer 1

您当前的解决方案是为二次输入字符串或O的大小（N^2）

您可以通过计算每个字符的出现更有效地解决这个问题字符串，然后计数可以与此字符来创建子串的数目。

例如，如果一个字符发生的4倍，则这导致3 + 2 + 1 = 6子串。

可以使用下面的公式这个：((n-1) * n)/2

这会使算法的复杂度下降到O（n），因为为了统计每个字符，你只需要遍历一次字符串。

我相信这个代码应工作：

public static void main(String[] args) { 
    String str = "xyzxyzxyzxyz"; 
    Map<Character, Integer> map = new HashMap<>(); 
    for (char c : str.toCharArray()) 
    { 
     Integer count = map.get(c); 
     if (count == null) 
      count = 0; 
     map.put(c, count + 1); 
    } 
    int sum = 0; 
    for (int n : map.values()) 
     sum += ((n - 1) * n)/2; 
    System.out.println(sum); 
}