【C语言】数据结构-----字符串匹配之KMP算法-创新互联
目录
算法简介
匹配原理
第一次匹配
第二次匹配
第三次匹配
第四次匹配
可能失配位置----next数组求解
next数组的由来
next数组的用法
next数组代码的实现
KMP算法的实现
示例：完整的代码
KMP算法与BF算法相比较
算法简介
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特--莫里斯--普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。
这一期我会详细讲解KMP算法的使用方法，以及与BF算法之间的不同和优点，一起来看看吧！
匹配原理对于KMP算法，我们需要知道模式串里面前缀和后缀之间有多少个相同的字符，比如abcdabwq，这里前后相同大的字符个数是2个，设为next[ j ]，其中 j 为可能失配的位置。其中next[ j ]的值只跟模式串有关。
第一次匹配假设
主串：a b c d a b e a b c d a b
模式串：a b c d a b d
第二次匹配a b c d a b e a b c d a b d
a b c d a b d
很明显第六个出现了不同，在此之前前面出现相同的字符大个数是2。
第三次匹配前面我们知道模式串出现相同字符大个数为2，此时直接把子串相同字符的位置移动到以下位置：
a b c d a b e a b c d a b d
a b c d a b d
这里我们可以发现主串跟模式串中的第三个字符不相匹配，所以此时要把模式串的第一个位置与 e 进行比较
第四次匹配a b c d a b e a b c d a b d
a b c d a b d
很显然此时模式串的第一个字符与主串不匹配，所以需要将主串的比较位置往后移动一位，模式串也是一样往后移动一位，再次比较
a b c d a b e a b c d a b d
a b c d a b d
此时匹配成功，返回主串匹配成功第一个字符的位置（主串中 a 的位置）
以上就是KMP算法的匹配过程，我们发现这个过程不好理解，看上去比较繁琐，确实，因为KMP算法的效率比较高，当然省时会费脑。那我们怎么去求解模式串中可能失配位置的 next 数组呢？这个是相对比较难的。接着往下看！
可能失配位置----next数组求解看懂上面的匹配过程我们不难发现，第一次匹配到第二次匹配，我们没有去一个一个来匹配，而是直接跳到相同字符位置去进行匹配，中间直接跳过了一些无必要匹配过程。这里我们就用到了KMP算法中的next数组，那这里怎么得出next数组呢？
next数组的由来对于 a b c d a b d
1.首位字符 a 前面是没有字符的，故没有前缀也没有后缀，那么其next数组值为-1，即next[ 0 ]=-1
2.对于第二个字符b 其前面的前缀和后缀都是字符a都是同一个，所以不能表示前缀与后缀相等，故其next数组值为0,即next[1]=0
3.对于第三个字符c其前面前缀a , b不相等，所以没有前缀与后缀相等，故next[2]=0
4.对于第四个字符d其前缀有a,ab,后缀有bc,c，故前缀与后缀都不相等，所以next[3]=0
5.对于第五个字符a其前缀有a,ab,abc后缀有bcd,cd,c同样也是不相等，所以next[4]=0
6.对于第六个字符b其前缀有a,ab,abc,abcd，后缀有bcda,cda,da,a，这里我们发现有一个前缀与后缀相等那就是 a 所以next[5]=1
7.对于第七个字符d其前缀有a,ab,abc,abcd,abcda,后缀有bcdab,cdab,dab,ab,a其相等的前缀和后缀一共有两个，所以next[6]=2
next数组的用法a b c d a b d
next[0] next[1] next[2] next[3] next[4] next[5] next[6]
next数组的值: -1 0 0 0 0 1 2
(next数组的值只跟模式串有关，与主串无关)
a b c d a b e a b c d a b d
a b c d a b d
第一次匹配完后，此时的模式串下标 j=6,指到第六个字符，所以此时可以知道next[6]值为2，那么我们可以直接令j=next[6]=2,所以就会出现第二次匹配，同时主串的位置 i 不变
a b c d a b e a b c d a b d
a b c d a b d
此时匹配的位置是c的位置也就是j=2的位置，这里我们发现此时j=2时e与c不匹配，所以查看j=2时next[2]=0,所以第三次匹配充j=0这个位置开始，同时主串的位置 i 不变
a b c d a b e a b c d a b d
a b c d a b d
以此类推…………
next数组代码的实现next数组用法规律总结：
如果遇到next[j]=0时，此时主串开始匹配位置i不变，模式串的位置从j=0，也就是开头进行匹配
如果遇到next[j]=-1时，此时主串的位置移动到下一位，也就是i++,同时模式串的位置也回溯到首位字符位置，再进行匹配
如果遇到next[j]>0的数字，此时主串的位置i 不变，模式串的位置移动到j=next[j]的位置再进行匹配
当然，如果主串与模式串的字符匹配相同的话那么主串的位置向后移动一位 i++,模式串的位置也是向后移动一位 j++
我们可以发现next数组只有三种数值：-1 0 >0的数，通过next数组的规律来写下这段代码
void next(const char* t, int* n)//字符串t是表示模式串,数组n既是next数组，在主函数里面我们可以用指针去申请内存来建立next数组
{
int j = -1, i = 0;//其中j是表示前缀位置，i是表示后缀位置
n[0] = -1; //进行初始化
while (i< strlen(t))//如果后缀的位置小于模式串的长度才可以进行循环
{
if (j == -1 || t[i] == t[j])
{
i++;
j++;
n[i] = j;
}
else//此时是没有找到相同的前缀和后缀，所以j=next[j]
j = n[j];
}
}如果理解了next数组，那实际上KMP算法也是基本理解了
示例：输出字符串 a b c d a b d 的next数组
#include#include#includevoid next(const char* t, int* n)
{
int j = -1, i = 0;
n[0] = -1;
while (i< strlen(t))
{
if (j == -1 || t[i] == t[j])
{
i++;
j++;
n[i] = j;
}
else
j = n[j];
}
}
void put(int* p,char *ss)
{
for (int i = 0; i< strlen(ss); i++)
printf("%d ",p[i]);
}
int main()
{
char a[100] = "abcdabd";
int* n =(int*)malloc(sizeof(int)*strlen(a));//通过内存申请创建数组
next(a, n);
put(n,a);
return 0;
} 结果如下：
int kmp(const char* a,const char* b,int *next)
{
int i = 0, j = 0;
while (i< strlen(a))
{
if (a[i] == b[j]||j==-1)//如果主串与模式串该字符相匹配，或者j=next[0]=-1时，也就是模式串的第一个字符不与主串该字符匹配相同时，主串与模式串同时向后移动一位
{
i++;
j++;
}
else if(a[i]!=b[j])//如果主串与模式串不相同时，模式串下标j赋值为next[j]
{
j = next[j];
}
if (j == strlen(b))//如果j等于模式串长度时，就说明匹配成功，返回主串位置i-j
return i-j;
}
return -1;
}我们可以看出KMP代码并不是很长，相较于BF算法也就是多了个关键的next数组。其他很大部分都是没什么变化的，也就是在BF算法的代码上面稍微改了改一点点.
示例：完整的代码#include#include#includevoid next(const char* t, int* n)
{
int j = -1, i = 0;
n[0] = -1;
while (i< strlen(t))
{
if (j == -1 || t[i] == t[j])
{
i++;
j++;
n[i] = j;
}
else
j = n[j];
}
}
int kmp(const char* a,const char* b,int *next)
{
int i = 0, j = 0;
while (i< strlen(a))
{
if (a[i] == b[j]||j==-1)
{
i++;
j++;
}
else if(a[i]!=b[j])
{
j = next[j];
}
if (j == strlen(b))
return i-j;
}
return -1;
}
int main()
{
char a[100] = "abcdabd";
char b[100] = " abcdabeabcdabd";
int* n =(int*)malloc(sizeof(int)*strlen(a));
next(a, n);//对数组n(也就是上面讲的next数组)进行赋值
printf("%d\n", kmp(b, a, n));
return 0;
} 输出结果：
BF算法代码：
int bf(char* a, char* b)
{
int i, j;
i = j = 0;
while (a[i] != '\0')
{
if (a[i] == b[j] && b[j] != '\0')
{
i++;
j++;
}
else
{
i = i - j + 1;
j = 0;
}
if (j == strlen(b))
{
return i - j + 1;
}
}
return -1;
}KMP代码上面有。对比代码量就知道，BF算法的代码量是比较少的，但是运算效率低下，而KMP代码量比较多，但是运算效率比较高，KMP算法是相对比较先进的算法。
好了这一期就讲了怎么使用KMP算法来帮助我们去解决字符串匹配的问题，掌握好 KMP算法将来会有很大用处，我是守约斯维奇，喜欢的话给个关注吧
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
文章标题：【C语言】数据结构-----字符串匹配之KMP算法-创新互联
文章位置：http://scyanting.com/article/dceojd.html
