字符串查找

在编写代码时，我们时常会遇到字符串的相关操作，而字符串查找更是屡见不鲜。如图1所示查找W在S中的位置，假设我们只返回第一次匹配成功的索引值。

普通方法

普通做法是一一比较，若遇到字符不一致时，指针i回到起始匹配字符的下一个字符，而指针j则回到起始位，即i=i-j+1, j=0。如此操作直到匹配成功或遍历完字符串。
如图2所示

KMP算法

一种比较高效的字符串匹配算法KMP，全称Knuth-Morris-Pratt字符串查找算法。该算法的精妙之处在于利用了匹配串已匹配部分的信息来移动指针i，这样可以避免一些不必要的搜索。
如图3所示，当匹配不一致时，我们已经判断出S[1]~S[2]不会于W匹配，所以可以直接跳过。

若发现匹配子串中存在前后缀子串一致的时候，可以将指针j指向最长匹配前缀的下一个字符。如图4所示，匹配子串adbad的最长匹配前后缀为ab，所以W从第三个字符开始匹配即可。

而当时，只需要将指针i前移一位即可。
如此操作直到匹配成功或者遍历完S为止。

KMP的关键部分是要获得W的所有前缀子串的最长匹配真前后缀，即创建一个部分匹配表。首先需要弄清楚字符串的真前后缀。真前缀为从首位开始的长度小于主字符串的所有子串，真后缀则是以末尾字符为结束的长度小于主字符串的所有子串。例如，字符串abc的所有真前缀为a/ab，所有真后缀为bc/c。那么，最长匹配前后缀就是前后缀中最长的相同子串，例如adbad的最长前后缀为ad。
那么，W的部分匹配表为

常见写法是记录该字符之前的子串的最长匹配真前后缀，如下图所示。