首页 > 代码库 > KMP算法
KMP算法
1、概述
KMP算法是一种改进的字符串匹配算法,关键在于利用匹配失败后的信息,尽量减少模式串与主串的次数。
2、算法原理
举个简单的例子:主串为“BBC ABCDAB ABCDABCDABDE”,匹配串为“ABCDABD”
通常我们比较字符串,从头开始,第一个字符不匹配时,向后移匹配串。
当匹配串与主串匹配时,比较主串和匹配串的下个字符
当匹配失败时,通常我们会会将匹配串后移一个字符,并重新开始匹配
这样的时间复杂度为O(N*M),而仔细观察,可以发现,匹配串中只有两个B,且都已经与主串,换句话说,主串在“ABCDAB”中不可能有第三个“B”,所以第一个“B”的下一个匹配点应该是在“ABCDAB”中的第二个B,即匹配串与主串匹配的第二个“B”
这样可以减少字符比较次数,那么这个后移位数应该如何确定,如何能最优呢
移动位数 = 已匹配的字符数 - 对应的部分匹配值
"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例,
- "A"的前缀和后缀都为空集,共有元素的长度为0;
- "AB"的前缀为[A],后缀为[B],共有元素的长度为0;
- "ABC"的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;
- "ABCD"的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为0;
- "ABCDA"的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共有元素为"A",长度为1;
- "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为"AB",长度为2;
- "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共有元素的长度为0。
参考资料
博客 《字符串匹配的KMP算法》http://kb.cnblogs.com/page/176818/
KMP算法