3

我有如下蛮力字符串模式搜索算法：

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：“商店”

感谢您的时间和帮助

4

2 回答 2

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)

ETC...

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

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

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

最好的情况是O(n)匹配在m.

于 2013-03-22T06:39:32.540 回答
0

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

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

请注意，同一算法不能有 2 个 Big-O。

看来您正在应用蛮力窗口移位算法，

时间 = (m-n+1)m

最坏的情况是当你有 m=1, O(nm)

最好的情况是当你有 m=n, Ω(m)

于 2013-03-22T07:00:31.160 回答