string - 暴力字符串模式匹配平均分析

Question

我有如下的强力字符串模式搜索算法:

public static int brute(String text,String pattern) {
 int n = text.length();    // n is length of text.
 int m = pattern.length(); // m is length of pattern
 int j;
 for(int i=0; i <= (n-m); i++) {
    j = 0;
    while ((j < m) && (text.charAt(i+j) == pattern.charAt(j)) ) {
       j++;
    }
    if (j == m)
     return i;   // match at i
  }
  return -1; // no match
} // end of brute()

作者在分析上述算法时提到了最坏情况和平均情况。

我了解最坏情况下的性能，但对于平均作者如何得出 O(m+n) 性能？此处需要帮助。

在最坏的情况下，蛮力模式匹配的运行时间为 O(mn)。

大多数普通文本搜索的平均时间为 O(m+n)，这非常快。

更一般情况的示例: T:“字符串搜索示例是标准的” P:“商店”

感谢您的时间和帮助

Answer 1

他指的 O(m+n) 是在正常情况下会发生的部分匹配。

例如，对于您的正常情况，您将得到:

T: "a string searching example is standard" 
P: "store"

迭代:

 O(38 + 5) == 43
 a -     no match (1)
 space - no match (2)
     s     - match (3)
     t     - match (4)
     r     - no match (5)
 t     - no match (6)
 r     - no match (7)
 i     - no match (8)
 n     - no match (9)
 g     - no match (10)
 space     - no match (11)

等...

我缩进了内部循环以使其更易于理解。

最终您检查了所有 m，即 O(m)，但部分匹配意味着您检查了所有 n 是 O(n)(找到完全匹配)，或者至少有足够的字符等于 n 中的字符数量(仅部分匹配)。

总体而言，这导致平均 O(m+n) 时间。

最好的情况是 O(n) 如果匹配是在 m 的最开始。