KMP算法（学习记录）

2019-11-10 18:31:22

字体：大中小

来源：转载

供稿：网友

KMP算法之前感觉已经理解了，但过了一段时间，感觉又不知是什么，现在重新学习下，做下记录。

目的：匹配字符串遇到不匹配的时候不用回溯，而是通过一个数组（next[]/nextval[]）确定主串不匹配字符接下来和匹配串哪个位置的字符进行比较。（假设位置都从0开始）匹配过程此时匹配到6位置，发现不匹配

这里写图片描述匹配串滑动尽可能的远的距离

实际上是找到匹配串不匹配位置（6）前的字符串即abadab前缀串和后缀串的最大公共部分的位置

这里写图片描述可以看出，abadab的最大公共部分是ab，所以主串位置6的字符d需要和匹配串位置1后面的字符a比较

继续比较字符的位置=前缀后缀串最大公共部分的长度（ab的长度为2，b的位置是2-1，b后面字符的位置为2-1+1=2）

现在求数组next[]，设匹配串是s[0…n] next[0]=-1，-1代表主串某字符和匹配串第一个字符匹配失败 next[1]=0 , 一个字符的没有前缀和后缀，其长度为0 假设next[i] = x ，即匹配串0到j-1前后缀的最大公共部分是0到x-1,此时串的状态见图这里写图片描述

现在求next[i+1],即求0到i前后缀的最大公共部分，其组成必定是下图这样的，相当于求位置0到i-1字符串的前后缀的公共部分 && s[i]==s[?]成立的最大长度

这里写图片描述

当位置i和位置x的字符相等时，显然？=x，最大公共部分长度为x+1，当位置i和位置x的字符不相等时，即长度为x的公共串不符合要求，需要取相对小些的公共部分，这个肯定也是0到x-1的前后缀最大公共部分，即next[x],此时next[i]和next[?]（此时？=next[x]）进行比较，不相等表示还要取更小的公共部分（即0到next[x]-1的前后缀最大公共部分），重复这个过程，直至s[i]==s[?]或者?==-1为止，-1代表找不到公共部分，即next[i]=0

// 输入s[0...n] 空数组next[0...n] 求next[] int i=0,x=-1; next[i]=x; while(i<=n) { if(x==-1 || s[i]==s[x]) next[++i]=++x; else x=next[x]; }

现在发现个问题，比如next[i]=x,表示的是主串与匹配串匹配是在匹配串的位置i处发现不匹配，然后匹配串尽量右移，使主串的那个字符与匹配串的位置x的字符进行比较，如果匹配串位置x的字符和位置i的字符一样呢，肯定又是不匹配，主串字符再与匹配串位置next[x]的字符进行匹配，这不是浪费次数嘛这里写图片描述

现在可以改进一下数组next,即当s[i]和s[next[i]]一样时，next[i]=next[next[i]],这个就是nextval[]数组

这里写图片描述

// 输入s[0...n] 空数组nextval[0...n] 求nextval[] int i=0,x=-1; nextval[i]=x; while(i<=n) { if(x==-1 || s[i]==s[x]) { ++i;++x; if(s[i]==s[x]) nextval[i]=nextval[x];//增加一个判断即可 else nextval[i]=x; } else x=next[x]; }

KMP函数

//输入str[0...size] s[0....n] int i=0;j=0; while[i<=size && j<=n] { if(j==-1 || str[i]==s[j]){++i;++j;} else j=nextval[j]; } if(j>n) return i-n-1;//匹配成功 else return -1; //匹配失败

这里写图片描述