KMP算法之我见

预备谈谈下面这些，可能有补充

KMP算法的用途；

KMP算法之前的暴力；

KMP算法预备知识与概念；

KMP算法模板：

KMP算法的习题。

1.KMP算法的用途：

主要用于模式匹配（字符串匹配）。给定一个长的字符串（target string）和一个短的字符串（pattern string），要求判断pattern string是否是target string的子串，若是，则返回子串的首个字符的下标，若否，则返回-1。

2.KMP算法之前的暴力：

解决这个问题最常想到的办法是brute force，即从target string第一个字符开始与pattern字符比较，如果相等则比较target string和pattern string的下一个字符，若不等则返回到target string中相等的字符的下一个字符。换句话说，假设我们用target和pattern分别表示两个字符串的指针，那么每一次比较不管两个string匹配到何种程度，只要不是完全匹配，那么target永远只能增加1，这个算法的复杂度为O（mn）。

m = strlen（target string）

n = strlen（pattern string）

而这个接近n²的算法在n与m较大时显得非常效率低下。于是KMP算法粉墨登场，其实KMP算法与BF算法的区别在于KMP算法巧妙地消除了指针i的回溯问题，只需要确定下次匹配j的位置即可，是的问题复杂度由O（mn）下降到O（m+n）

巴特西

KMP算法之我见

1.KMP算法的用途：

2.KMP算法之前的暴力：

最新文章

热门文章