概念

KMP是一种模式匹配算法。

模式匹配

模式匹配是数据结构中字符串的一种基本运算，给定一个子串，要求在某个字符串中找出与该子串相同的所有子串，这就是模式匹配。
假设P是给定的子串，T是待查找的字符串，要求从T中找出与P相同的所有子串，这个问题成为模式匹配问题。P称为模式，T称为目标。如果T中存在一个或多个模式为P的子串，就给出该子串在T中的位置，称为匹配成功；否则匹配失败。

KMP算法概念

Knuth-Morris-Pratt算法（简称KMP），是由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的一个改进算法，消除了朴素的模式匹配算法中回溯问题，完成串的模式匹配。
算法思想：
设目标串为s，模式串为t， i、j 分别为指示s和t的指针，i、j的初值均为0。
若有 si = tj，则i和j分别增1；否则，i不变，j退回至j=next[j]的位置 ( 也可理解为串s不动，模式串t向右移动到si与tnext[j]对齐 )；
比较si和tj。若相等则指针各增1；否则 j 再退回到下一个j=next[j]的位置(即模式串继续向右移动 )，再比较 si和tj。
依次类推，直到下列两种情况之一：
1)j退回到某个j=next[j]时有 si = tj，则指针各增1，继续匹配；
2)j退回至 j=-1，此时令指针各增l，即下一次比较 si+1和 t0。
记模式P的长度为m,目标T的长度为n,则KMP匹配算法的时间复杂度的分析如下：
整个匹配算法由Find()和GenKMPNext()两部分算法组成。在Find()中包含一个循环,J的初值为0，每循环一次j的值严格家1，指导j等于n时循环结束，故循环执行了n次。在GenKMPNext()中，表面上有两重循环，时间复杂度似乎为O(),其实不然，GenKMPNext()的外层循环恰好执行了m-1次；另外，j的初值为-1，外层循环中，每循环一次，j的值就加1，同时，在内层循环中j减小，但最少不会小于-1，因此内层循环中j=next[j]的语句的总的执行次数应小于或等于j的值在外层循环中被加2 的次数。即在算法GenKMPNext()结束时，j=next[j]的执行总次数小于等于m-1次。
综上，对于长度为m的模式和长度为n的目标T的模式匹配，KMP算法的时间复杂度为O(m+n)。

下面是一个KMP算法在匹配时的过程
目标串为:[a,b,a,b,c]
模式串为:[a,b,c]