11

我还想知道哪种算法在查找另一个字符串中所有出现的字符串时具有最坏情况的复杂性。似乎 Boyer–Moore 的算法具有线性时间复杂度。

4

4 回答 4

11

KMP 算法具有线性复杂性，可用于查找字符串中模式的所有出现，如 Boyer-Moore 算法¹。如果你试图在像“aaaaaaaaa”这样的字符串中找到像“aaaaaa”这样的模式，一旦你有了第一个完整的匹配，

aaaaaaaaa
aaaaaa
 aaaaaa
      ^

边界表包含以下信息：模式前缀的下一个最长可能匹配（对应于模式的最宽边界）仅短一个字符（完全匹配相当于在模式末尾之后的不匹配这方面）。因此，模式被进一步移动了一个位置，并且由于从边界表中知道模式的所有字符可能除了最后一个匹配，下一个比较是在最后一个模式字符和对齐的文本字符之间进行比较。在这种特殊情况下（在n中找到m的出现），这是朴素匹配算法的最坏情况，KMP 算法只比较每个文本字符一次。

在每个步骤中，至少有一个

  • 比较的文本字符的位置
  • 模式的第一个字符相对于文本的位置

增加，并且永远不会减少。比较的文本字符length(text)-1的位置最多可以增加，第一个模式字符的位置最多可以增加length(text) - length(pattern)，因此该算法采取的2*length(text) - length(pattern) - 1步骤最多。

预处理（边界表的构建）最多需要步骤，因此总体复杂度为 O(m+n)，如果是模式的长度和文本的长度，则2*length(pattern)不再m + 2*n执行任何步骤。mn

¹ 请注意，如果需要所有匹配，通常提出的 Boyer-Moore 算法对于周期性模式和文本（如m和n ）的最坏情况复杂度为 O(m*n) ，因为在完全匹配后，

aaaaaaaaa
aaaaaa
 aaaaaa
      ^
  <- <-
 ^

将重新比较整个模式。为了避免这种情况，您需要记住模式的前缀在完全匹配后的移位之后仍然匹配多长时间，并且只比较新字符。

于 2012-02-07T22:24:51.980 回答
4

在http://en.wikipedia.org/wiki/Knuth-morris-pratt上有一篇关于 KMP 的长文章，最后说

由于算法的两个部分分别具有 O(k) 和 O(n) 的复杂度，因此整个算法的复杂度为 O(n + k)。

无论 W 或 S 中有多少重复模式，这些复杂性都是相同的。（结束引用）

因此，KMP 搜索的总成本与字符串和模式的字符数成线性关系。我认为即使您需要在字符串中找到多次出现的模式，这也成立 - 如果没有，只需考虑搜索 patternQ，其中 Q 是文本中未出现的字符，并记下 KMP 状态显示的位置它已将所有内容与 Q 匹配。

于 2012-02-07T19:52:02.917 回答
3

您可以计算 Pi 函数中的字符串O(length)。KMP 构建一个具有长度的特殊字符串n+m+1，并在其上计算 Pi 函数，因此在任何情况下复杂度都是O(n+m+1)=O(n+m)

于 2012-02-07T19:39:11.663 回答
0

如果您考虑一下，匹配模式的最坏情况是当发生不匹配时您必须访问 LPS 数组的每个索引。例如，"aaaa"创建 LPS 数组的模式[0,1,2,3]使之成为可能。

现在，对于文本中的最坏情况匹配，我们希望最大化这种不匹配，迫使我们访问 LPS 数组的所有索引。那将是具有重复模式的文本，但最后一个字符不匹配。例如，"aaabaaacaaabaaacaaabaaac"。

设文本的长度为n，图案的长度为m。这种模式在文本中出现的次数是n/m。对于这些事件中的每一个，我们都在进行m比较。不要忘记我们也在遍历n文本的字符。

因此，KMP匹配的最坏情况时间是O(n + (n/m)*m)，基本上是O(n)。

总的最坏情况时间复杂度，包括 LPS 创建，将是O(n+m).

KMP代码（供参考）：

void createLPS(char[] pattern,int[] lps){
        int m = pattern.length;
        int i=1;
        int j=0;
        lps[j]=0;
        while(i<m){
            if(pattern[j]==pattern[i]){
                lps[i]=j+1;
                i++;
                j++;
            }else{
                if(j!=0){
                    j = lps[j-1];
                }else{
                    lps[i]=0;
                    i++;
                }
            }
        }
    }

 List<Integer> match(char[] str, char[] pattern, int[] lps){
        int m = pattern.length;
        int n = str.length;
        int i=0, j=0;
        List<Integer> idxs = new ArrayList<>();
        while(i<n){
            if(pattern[j]==str[i]){
                j++;
                i++;
            }else{
                if(j!=0){
                    j = lps[j-1];
                }else{
                    i++;
                }
            }
            if(j==m){
                idxs.add(i-m);             
                j = lps[j-1];
            }
        }
        return idxs;
    }
于 2022-02-17T17:25:49.833 回答