目录1 .模式匹配2 .模式匹配算法1 .朴素模式匹配算法2. KMP算法1 ).KMP算法优势2 ).KMP算法原理3 ).next数组结构4 ) .
一.模式匹配
两个字符串Str='abdabcde； modStr='abcd '； 假设，如果要在Str中查找与modelStr相等的子列，则Str称为主列，modelStr称为模式列。 在搜索过程中，如果从Str的第一个字符进行比较，并找到与modelStr相同的子字符串，则函数返回modelStr字符串的第一个出现位置，否则返回-1。 以上过程称为模式匹配。
2 .模式匹配算法模式匹配算法。 最广为人知的是两种算法，一种是简单暴力的BF算法，另一种是非常高效的KMP算法。 以下详细说明两种方法。
1 .朴素模式匹配算法BF算法是朴素模式匹配算法的经典。 该算法的主要思想是从主字符串的第一个字符与模式串的第一个字符进行比较，相等时继续比较，不相等时从主字符串中不相等的位置与模式串的第一个字符进行比较。
指针I指向主列，j指向模式列，如果匹配失败，则I移动的位置为i=i - j 1。
所有字符串匹配后，指针j指向模式串末尾的下一个字符串，在进行匹配的过程中，每当匹配失败时，I指针都会进行不必要的回溯，可见该回溯过程极大地浪费了时间。
2. KMP算法1 ).KMP算法的优越性论述了前述BF算法的实现和BF算法的低效率，KMP算法是对BF算法的改进，如果进行模式匹配时字符不同，则为I点
2 ).KMP算法的原理字符串Str='acabaabaabcacaabc '； modStr='abaabcac '； 作为例子进行说明。
如果i=8，j=6，则匹配失败：根据BF算法，I指针追溯到4的位置，开始比较。 但是，需要这个I的回溯吗？ 很明显，不需要duck。
观察一下，由于j1=j4、j2=j5且i3=j1、i4=j2，所以完全不需要追溯到I指针4的位置。 根据上述等式关系，只需将j指针的位置移动到j4的位置并重新开始匹配即可。
再看另一个例子， str=" aababcaad " MODS tr=" babc "，i=6，j=4时发生失配，但由于j1=j3，所以直接将j指针移动到j4的位置进行匹配
再看最后一个例子，发生str=“aacabcd”、modStr=“abcd”、失配时，怎么操作？
发生失配时，将I指针向后移动1位，继续比较。
综合上述例子可知，模式列中存在文字相同的要素，模式列的子列中构成了前缀和后缀。 并且，在失配之后`对于指针的移动存在一定的规律，引出了用于存储模式匹配失配的next数组的概念。
3 ).next数组的结构从上述例子中可以看出，存储在next[]数组中的内容是用于在模式列与目标列匹配失败时查找模式列的回溯目的地的数组。
如何计算next数组？ 其中最重要的概念是最大前缀和最大后缀。
表达式这样表示最大前缀和最大后缀，但实际上怎么解呢？ str='abaabcac '以此字符串为例，表示前缀和后缀。
对于该字符串，其前缀和后缀是这样的，所以其最大前缀=最大后缀的字符串是a；
接着，根据这个最大前缀=最大后缀的概念，进行失配后的图案列的回溯的位置计算。
将图案列设为abaabcac(j (假设将j指示的位置设为当前匹配位置，在当前位置失配，求出在当前位置失配的回溯位置，将j指针的前方字符串设为计算回溯位置的子列) )
1.j=1失配(因为j=0，所以next[j]=0) )。
2.j=2失配(无前后缀，其他情况) )。
3.j=3失配(前缀不等和后缀) ) ) ) ) )。
4.j=4失配(最大前缀=最大后缀，因此k=2) )。
5.j=5失配
6.j=6失配(最大前缀ab=最大后缀ab，因此k=3) )。
7.j=7失配
8.j=8失配
以上是next数组的求解方法，但字符串下的表一般从0开始，所以对于next数组的元素-1
现在，next数组解决了。 有关如何使用next数组进行模式匹配的信息，请继续阅读以下内容。
4 ) .使用next数组匹配的过程本节介绍模式匹配如何使用next数组进行模式匹配。
str='acabaabaabcacaabc '； modStr='abaabcac '； 例如，字符串的下标从0开始，说明：
1 .第一个匹配(i=1，j=1的位置发生失配) ) ) ) ) ) )。
可以看出，根据next数组，将j指针追溯到j0的位置进行重新匹配。
2 .第二次匹配(i=
1,j=0位置发生失配)next数组中没有相关跳转位置，所以i指针后移一位，开始匹配。
3.第三次匹配(i=7,j=5位置发生失配)
根据next数组，可知j回溯到 2的位置重新开始匹配
4.匹配成功
以上就为KMP算法的匹配过程。