KMP算法详细推导和理解

Blog

字符串匹配的朴素做法

（称被匹配串为str，匹配串为pat）
朴素的字符串匹配算法就是每次将pat后移一位，然后继续从pat的第一位开始比较。

但其实我们已经获取了信息『不匹配位置的前面的字符都是匹配的』.
朴素做法并没有利用到这个信息，而KMP就是要利用这个信息加快速度。

KMP如何利用已有信息

1. 首先pat必然是要后退，关键在于后退几位。
2. 设我们已经知道匹配的子串是『ABCADAB』，这代表了两层含义：
   
   1. pat的前7位是『ABCADAB』，pat是『ABCADABxxx』
   2. str在当前匹配位置的7位子串是『ABCADAB』，str是『xxxABCADABxxx..xx』
3. 若用朴素的做法将pat后退的过程中：
   
   1. 后退1步：str在当前匹配位置是『BCADABxxxx』，pat是『ABCADABxxx』，第一位就不匹配
   2. 后退2步：str是『CADABxxxxx』，pat是『ABCADABxxx』，第一位就不匹配
   3. 后退3步：str是『ADABxxxxxx』，pat是『ABCADABxxx』，第一位匹配，第二位不匹配
   4. 后退4步：str是『DABxxxxxxx』，pat是『ABCADABxxx』，第一位就不匹配
   5. 后退5步：str是『ABxxxxxxxx』，pat是『ABCADABxxx』，第一位和第二位都匹配，后面是否匹配无法根据现有信息得到，需要进一步获得str后续的子串是什么。
4. 我们可以发现：朴素的匹配算法中后退1-4步都是不匹配的，而这4种不匹配的情况都可以根据已得信息（即步骤2获得信息）判断出来其不匹配。当后退5步的时候，无法根据已得信息得知是否匹配，就需要进一步进行匹配。
5. 而KMP算法的目标就是利用已得信息（即步骤2获得的信息）来消除后退1-4步这些无用匹配。

KMP的具体实现

1. 那么KMP具体怎么实现的呢？
   
   1. 仔细观察上例发现，当匹配的子串是『ABCADAB』时，后退1-4步无效，可以直接跳到后退5步
   2. 根据3.e的情况，后退5步时，str是『ABxxxxxxxx』，开头的两个字符是『ABCADAB』的后两位后缀『AB』。而pat是『ABCADABxxx』，前两位前缀正好是『AB』。
   3. 再结合后退1-4步的情况，我们发现所有后退的情况，str的开头都是匹配的子串『ABCADAB』的后缀；pat都是『ABCADAB』的前缀。
   4. 因此，只要我们遍历『ABCADAB』的所有的<前缀，后缀>对，找到相等且最长的前后缀对即可。
   5. 对于『ABCADAB』，相等且最长的前后缀对就是<前缀=AB，后缀=AB>，长度为2。而『ABCADAB』长度为7，因此我们可以直接后退7-2=5步即可。
2. 因此，KMP的思想就是：找到匹配子串相等且最长的前后缀对，然后用匹配子串的长度减去前后缀对的长度，即得到要后退的步数。
3. 注意，匹配的子串必然是pat的前缀，而且pat的每一个前缀都有可能是匹配的子串。所以我们只需提前对pat子串进行一次处理即刻，记录下pat的每个前缀作为匹配的子串时，相等且最长的前后缀对的长度即可。（即代码里的next数组）

KMP的实现代码

附上我用Python实现的KMP算法的代码：Dounm/Fun-Programs/string-matching/kmp.py