前言

字符串匹配是计算机的基本任务之一。

KMP算法的思想是，设法利用已知的匹配信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。

做法：针对搜索词，算出一张《部分匹配表》（Partial Match Table）。

已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。查表可知，最后一个匹配字符B对应的"部分匹配值"为2，因此按照下面的公式算出向后移动的位数：

移动位数 = 已匹配的字符数 - 对应的部分匹配值

文章来源: kunnan.blog.csdn.net，作者：iOS逆向，版权归原作者所有，如需转载，请联系作者。

原文链接：kunnan.blog.csdn.net/article/details/123698164