KMP模式匹配算法

1 KMP模式匹配算法原理

假设主串S=“abcdefab”，我们要匹配的子串T=”abcdex“，如果用朴素模式匹配算法，前5个字母，两个串完全相等，直到第6个字母，”f“与“x”不等，如图所示。

接下来按照朴素模式匹配算法，应该是按照上图的步骤2、3、4、5、6，即主串S中当$i=2、3、4、5、6$时，首字符与子串T的首字符均不等。

仔细观察就会发现，对于要匹配的子串T来说，“abcdex”首字母“a”与后面串“bcdex”中任意一个字符都不相等。也就是说对于步骤1来说前五位字符分别相等，意味着子串T的首字符“a”不可能与S串的第2位到第5位字符相等。所以，在上图中，步骤2、3、4、5的判断都是多余的。

当我们知道T串中首字符“a”与T中后面的字符均不相等的前提下，T串后面的字符均不相等的前提下，T串的“a”与S串后面的“c”“d”“e”也都可以在步骤1之后就可以确定是不相等的，所以在朴素模式匹配算法中步骤2、3、4、5没有必要，只保留步骤1、6即可，如图所示。

保留步骤6中的判断是因为在步骤1中$T[6]\ne S[6]$，虽然我们已经知道了$T[1]\ne T[6]$，也不能断定$T[1]$一定不等于