很抱歉，您没有提供需要改写的句子。请提供您希望改写的句子，我将为您改写为一个长尾词的。
- 内容介绍
- 文章标签
- 相关推荐
本文共计1295个文字，预计阅读时间需要6分钟。
KMP算法是一种高效的字符串匹配算法。它通过预处理待匹配的字符串，生成一个部分匹配表（也称为失败函数），来减少匹配过程中不必要的比较次数。下面是KMP算法的核心概念：
1. 什么是KMP算法？KMP算法是一种改进的字符串匹配算法。它通过预处理模式串，使得在匹配过程中即使发生不匹配，也能从上一个匹配点继续匹配，从而避免从头开始比较，提高匹配效率。
帮你简单捋捋KMP算法的精髓 KMP算法今天自己琢磨了一下KMP算法，总算是有了一点头绪，现在我就给大伙讲解一下KMP算法的精髓。
1.什么叫做KMP算法？KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。----百度百科
也就是说我们在库函数常用的一个函数strstr()它是时间复杂度比较大的一种求解方法，其实我们可以利用一些有用的信息来减少我们所需要匹配的次数，从而减少我们的时间复杂度。
现在我们要从一个主串里找到一个子串，假定主串叫major_str，i用来遍历主串，major_len用来记作主串的长度。子串叫sub_str，j用来遍历子串，sub_len用来记作子串的长度。往下我将用这些代号来说明我对KMP的剖析。
它的过程比较复杂，跟我们所说的BF算法有很大的不同，但是本质就是遍历主串的下标不会往后退，子串遍历我们按照一个特定的方式来确定下次从哪开始遍历，记下这个特定的位置就是我们重点要讲解的next数组。
现在最重要的就是我们要记下“遍历主串的下标不会往后退，子串遍历我们按照一个特定的方式来确定下次从哪开始遍历”这句话！
先来看个例子吧。
图一
图二
图三
它是我们主角，它要做的事就是将子串回到一个特定位置，下标代表了子串字符位置，0就是第一个字符，以次类推。这次匹配失败，下次回到哪匹配，就是数组的值，数组的值就是我刚刚说ab的长度。我说一下它的规则：
- 找到匹配成功的两个相等的最大长度真子串（不包含本身），开始是以0下标，结尾是j- 1为下标的真子串.这个真子串的长度就是数组要存的值；
- 我们记作next数组为next[]的形式，始终将next[0] = -1,next[1] = 0，next[2]..next[sub_len]就是我们要求得的数据;
- "abcabcabcdabacbeabca"的next数组为多少？
- "aaaaaab"的next数组为多少？
- "ababababcdabcdcd"的next数组为多少？
之前给大伙手动求解，但是你要把它放到程序里，你还能用简单的方法把next数组值求出来吗？如果是按我们刚刚讲的，那这求解next数组不也变成了BF算法了，所以我们得另辟蹊径。
这个是个粗略的推导：
判断当前字符与它回退到的next值的字符是否一致，如果一致下一个next值自加一，如果不一致则继续回退，退回到要么一致的情况，要么k == -1的情况（其实就是回到了开始位置）；
5. 代码实现（C语言） 1. KMP的过程//返回值是主串中第一次出现子串的位置，如果没有子串，则返回-1
int KMP(const char* major_str, const char* sub_str, int pos)//pos是指定一个开始位置匹配
{
assert(major_str);
assert(sub_str);
int major_len = strlen(major_str);
int sub_len = strlen(sub_str);
if (major_len == 0 || sub_len == 0)
return -1;
if (sub_len > major_len)//子串比主串还长，不用比了
return -1;
if (pos < 0)//开始比较的位置小于0，错误
return -1;
int* next = (int*)malloc(sizeof(int) * sub_len);
assert(next);
GetNext(sub_str, next, sub_len);
//遍历下标
int m = pos;//遍历主串
int s = 0;//遍历子串
while (m < major_len)
{
if ((s == -1) || (major_str[m] == sub_str[s]))//s == -1是刚开始就匹配失败
{
m++;
s++;
}
else
{
s = *(next + s);//回到next记录的位置
}
if (s == sub_len)//如果遍历完了子串，说明匹配成功
return (m - s);//返回主串匹配子串成功第一个的下标
}
return -1;
}
2. next数组的实现
j跟k的含义参考这张图
void GetNext(const char* sub_str, int* next, int sub_len)
{
assert(sub_str);
*next = -1;//初试化
if (sub_len > 1)//不能越界访问
*(next + 1) = 0;//初始化
int j = 2;//第三个元素，也就是当前位置
int k = 0;//从第二元素开始的下标，之前一个的位置
while (j < sub_len)
{
if ((k == -1)||(sub_str[j - 1] == sub_str[k]))//k == -1的情况是回到起始位置
{
next[i] = k + 1;
k++;
j++;
}
else
{
k = *(next + k);//k要回退到sub_str[j - 1] == sub_str[k]的情况
}
}
}
总结
- next的求解就是一个迭代运算，规则比较奇怪；
- KMP算法关键就是遍历主串的下标不会往后退，子串遍历我们按照一个特定的方式来确定下次从哪开始遍历；
本文共计1295个文字，预计阅读时间需要6分钟。
KMP算法是一种高效的字符串匹配算法。它通过预处理待匹配的字符串，生成一个部分匹配表（也称为失败函数），来减少匹配过程中不必要的比较次数。下面是KMP算法的核心概念：
1. 什么是KMP算法？KMP算法是一种改进的字符串匹配算法。它通过预处理模式串，使得在匹配过程中即使发生不匹配，也能从上一个匹配点继续匹配，从而避免从头开始比较，提高匹配效率。
帮你简单捋捋KMP算法的精髓 KMP算法今天自己琢磨了一下KMP算法，总算是有了一点头绪，现在我就给大伙讲解一下KMP算法的精髓。
1.什么叫做KMP算法？KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。----百度百科
也就是说我们在库函数常用的一个函数strstr()它是时间复杂度比较大的一种求解方法，其实我们可以利用一些有用的信息来减少我们所需要匹配的次数，从而减少我们的时间复杂度。
现在我们要从一个主串里找到一个子串，假定主串叫major_str，i用来遍历主串，major_len用来记作主串的长度。子串叫sub_str，j用来遍历子串，sub_len用来记作子串的长度。往下我将用这些代号来说明我对KMP的剖析。
它的过程比较复杂，跟我们所说的BF算法有很大的不同，但是本质就是遍历主串的下标不会往后退，子串遍历我们按照一个特定的方式来确定下次从哪开始遍历，记下这个特定的位置就是我们重点要讲解的next数组。
现在最重要的就是我们要记下“遍历主串的下标不会往后退，子串遍历我们按照一个特定的方式来确定下次从哪开始遍历”这句话！
先来看个例子吧。
图一
图二
图三
它是我们主角，它要做的事就是将子串回到一个特定位置，下标代表了子串字符位置，0就是第一个字符，以次类推。这次匹配失败，下次回到哪匹配，就是数组的值，数组的值就是我刚刚说ab的长度。我说一下它的规则：
- 找到匹配成功的两个相等的最大长度真子串（不包含本身），开始是以0下标，结尾是j- 1为下标的真子串.这个真子串的长度就是数组要存的值；
- 我们记作next数组为next[]的形式，始终将next[0] = -1,next[1] = 0，next[2]..next[sub_len]就是我们要求得的数据;
- "abcabcabcdabacbeabca"的next数组为多少？
- "aaaaaab"的next数组为多少？
- "ababababcdabcdcd"的next数组为多少？
之前给大伙手动求解，但是你要把它放到程序里，你还能用简单的方法把next数组值求出来吗？如果是按我们刚刚讲的，那这求解next数组不也变成了BF算法了，所以我们得另辟蹊径。
这个是个粗略的推导：
判断当前字符与它回退到的next值的字符是否一致，如果一致下一个next值自加一，如果不一致则继续回退，退回到要么一致的情况，要么k == -1的情况（其实就是回到了开始位置）；
5. 代码实现（C语言） 1. KMP的过程//返回值是主串中第一次出现子串的位置，如果没有子串，则返回-1
int KMP(const char* major_str, const char* sub_str, int pos)//pos是指定一个开始位置匹配
{
assert(major_str);
assert(sub_str);
int major_len = strlen(major_str);
int sub_len = strlen(sub_str);
if (major_len == 0 || sub_len == 0)
return -1;
if (sub_len > major_len)//子串比主串还长，不用比了
return -1;
if (pos < 0)//开始比较的位置小于0，错误
return -1;
int* next = (int*)malloc(sizeof(int) * sub_len);
assert(next);
GetNext(sub_str, next, sub_len);
//遍历下标
int m = pos;//遍历主串
int s = 0;//遍历子串
while (m < major_len)
{
if ((s == -1) || (major_str[m] == sub_str[s]))//s == -1是刚开始就匹配失败
{
m++;
s++;
}
else
{
s = *(next + s);//回到next记录的位置
}
if (s == sub_len)//如果遍历完了子串，说明匹配成功
return (m - s);//返回主串匹配子串成功第一个的下标
}
return -1;
}
2. next数组的实现
j跟k的含义参考这张图
void GetNext(const char* sub_str, int* next, int sub_len)
{
assert(sub_str);
*next = -1;//初试化
if (sub_len > 1)//不能越界访问
*(next + 1) = 0;//初始化
int j = 2;//第三个元素，也就是当前位置
int k = 0;//从第二元素开始的下标，之前一个的位置
while (j < sub_len)
{
if ((k == -1)||(sub_str[j - 1] == sub_str[k]))//k == -1的情况是回到起始位置
{
next[i] = k + 1;
k++;
j++;
}
else
{
k = *(next + k);//k要回退到sub_str[j - 1] == sub_str[k]的情况
}
}
}
总结
- next的求解就是一个迭代运算，规则比较奇怪；
- KMP算法关键就是遍历主串的下标不会往后退，子串遍历我们按照一个特定的方式来确定下次从哪开始遍历；