KMP 算法在最佳情况下的最小比较次数是多少？
问问题
2786 次
2 回答
4
最好的情况是您要查找的字符串正好位于文本字符串的开头。k在这种情况下，如果您要在一个字母字符串中寻找一个n字母字符串，那么最好的比较次数是k.
您还必须考虑根据您的k字母词计算表格的开销，这将让您知道如果找不到匹配项则要跳过哪些字母。无论如何，这种构造是在O(k).
于 2012-10-20T21:55:23.920 回答
1
好吧，在最佳情况下，最小比较次数是字符串的长度，这意味着您首先尝试找到匹配项。该算法是 O(n)，这意味着上限或最坏情况将进行 n 次比较，其中 n 是您正在搜索的字符串的长度。维基很不错。 http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
于 2012-10-20T21:56:22.260 回答