KMP串中的模式匹配算法及从next[]到nextVal[]
KMP串中的模式匹配算法
一般的匹配算法：
KMP基本概念引入：
但是,其实我们会发现，上面的中间两个匹配步骤是没有必要的，因为他们的第一个匹配字母就不相同，完全没有可比性，而当我们在第四次匹配的时候，其 实我们从模式串中就可得知，只有当模式串滑到这个地方的时候，它的匹配才是最有价值的，因为从模式串中我们可以得知，最后一个C的前一个字母是a，而在模 式串中的第二个字母b的前一个字母也是a，再无其他，从第一步匹配的结果我们可以得知，模式串中的最后一个字母c与主串中的b匹配失败(读者们是否注意 到，我们前面提到的，这个c的前一个字母是a哦)， 而从模式串中我们可以得知，即我们完全可以跳过上面匹配步骤的中间的两步，那是否读者在担心中间会错过原本可以匹配的呢，完全不必担心，因为在我们的模式 串中就记录了，前面就连一个能和a进行匹配的字母都没有。
那么，当某一轮匹配失败时，模式项的滑动位置如何确定，即模式项中的那一项来和主串的的b(黄色格子内)对齐，从而省略中间的比较项，我们可以将这一项的index设置为K，如上的模式项，K为2 注意在串中，数组的第一项是用来记录数据个数的。
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
如上所述，KMP算法的关键，即根据模式串找到那个K(下面列出K所需要满足的条件)(当主串中第i个字符与子串中第j个字符失配时)：
设主串为：s1s2……sn 子串为：p1p2……pn
则K的取值应满足：
----------------------》》》》》》》》》》》》》》》
归根结底，找模式串与串头重复的子串：
实例：
那么：如何找到模式串中的每一个元素的K，也即如图中的next数组：
代码敬上：
void get_next(SString T,int next[])
{ /* 求模式串T的next函数值并存入数组next 算法 4.7 */
int i=1,j=0;
next[1]=0;
while(i<T[0])
if(j==0||T[i]==T[j])
{
i;
j;
next[i]=j;
}
else
j=next[j]; /*精髓之处 当前面已经有了相似的比较的时候，直接借用前面的结果 两个大体的环境相似，则这两个大体的环境间就会存在相同的匹配环境，即已经记录的环境，如果错过了一些已经匹配了子串，则会导致K值比实际的要小，即后面的匹配必须依赖前面的匹配结果*/
}
上面代码解释：
</center>
1：j=0时，i和j都要相加并给next赋值
2：T[i] = T[j] ,i和j都要相加并给next赋值
如果上面两个都不满足，则需要将 j 往前指向，那么问题就来了，为什么不直接 j = 1，而需要将 next[j]的值赋给 j 呢，其实就如我在代码中所讲，不妨也举个栗子说明一下。
</center>
其实可以总结为一下几点，K的目的是定位偏移量的index，失配项的前面有几个与模式项的头部相等的，K就为这些数加1，而其实这几个数，正是我们所要跳过的。
KMP算法的劣势，其实，从寻找K的过程中我们就可以看出，KMP算法重度依赖模式串与主串存在许多部分匹配
KMP算法从next[]到nextVal[]
上面，我们谈到了一个模式串K值的记录数组next[]，详细可看那篇文章，其实，前面定义的next[]数组是有一定缺陷的，下面我面我将针对一种情况进行举例：
如上图，如果按照之前的方法所获取的next[]数组的话，当两个字符串匹配到上图的情况是，将会出现如下图的情况：
我们发现，从step1到step3所走的路都是浪费的，因为都是用同一个字母(a)和b去比，而这个计算机也是哼容易识别的，所以对于next[]的改进是行的通的。
究其原因，为什么我会说上面的3个步骤是白走的呢，以为这是三个连续的相等的a，因此我们可以从第一步直接跳到第四步，即：得到的数组next[j] = k，而模式串p[j] = p[k]，当主串中的s[i] 和 p[j] 匹配失败时，不需要再和p[k]比较，而直接和p[next[k]]进行比较，当然可以一直迭代往前。
即：
代码如下:
void get_nextVal(SString T, int nextVal[])
{
int i = 1, j = 0;
nextVal[1] = 0;
while( i <= T[0])
{
if(j == 0 || T[i] == T[j])
{
j ;
i ;
if(nextVal[i] == nextVal[j])
{
nextVal[i] = nextVal[j];
}
else
{
nextVal[i] == j;
}
}
else
{
j = nextVal[j];
}
}
}
注意，所求的永远是前一个的K(写给自己的)嘻嘻
您可能感兴趣的文章：
KMP串中的模式匹配算法及从next[]到nextVal[]
数据结构与算法JavaScript (五) 串(经典KMP算法)
php中字符串匹配KMP算法实现例子
用C 与Java代码实现KMP算法实例
三种字符串查找算法的Go实现
数据结构与算法JavaScript (四) 串(BF)
正则表达式二
正则表达式使用详解
正则表达式使用详解
正则表达式在网络编程中的运用