42|串的KMP模式匹配算法之实现与性能分析:代码实现简单
王健伟
你好,我是王健伟。
上节课我们针对串的 KMP 模式匹配算法配以了大量的图形进行了非常仔细的观察,而观察的目的,就是为了这节课代码的实现。
串的 KMP 模式匹配算法实现代码并不多,但只有你学好了上节课的内容,对该算法有详细的理解,才能理解本节这样写代码的含义。
KMP 模式匹配算法实现代码
KMP 模式匹配算法实现代码各式各样,有些实现方法虽然简洁,但并不好理解,我这里先以比较容易理解的方式进行代码实现。你可以先仔细读一遍。
void getNextArray( int next[])
{
if (length < 1)
return;
if (length == 1)
{
next[0] = 0;
return;
}
next[0] = 0;
next[1] = 1;
if (length == 2)
{
return;
}
int nextarry_idx = 2;
int max_pub_zhui = 0;
while (nextarry_idx < length)
{
int left_RMC_count = nextarry_idx;
int max_pub_zhui = left_RMC_count - 1;
int start1idx = 0;
int start2idx = left_RMC_count - max_pub_zhui;
int xhtimes = max_pub_zhui;
while (xhtimes > 0)
{
if (ch[start1idx] != ch[start2idx])
{
max_pub_zhui--;
start1idx = 0;
start2idx = left_RMC_count - max_pub_zhui;
xhtimes = max_pub_zhui;
continue;
}
else
{
start1idx++;
start2idx++;
}
xhtimes--;
}
next[nextarry_idx] = max_pub_zhui + 1;
nextarry_idx++;
}
return;
}
int StrKMPIndex(const MySString& substr, int next[], int pos = 0)
{
if (length < substr.length)
return -1;
int point1 = pos;
int point2 = 0;
while (ch[point1] != '\0' && substr.ch[point2] != '\0')
{
if (ch[point1] == substr.ch[point2])
{
point1++;
point2++;
}
else
{
if (point2 == 0)
{
point1++;
}
else
{
point2 = next[point2] - 1;
}
}
}
if (substr.ch[point2] == '\0')
{
return point1 - point2;
}
return -1;
}
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
0/2000
本文详细介绍了KMP模式匹配算法的实现和性能分析。作者王健伟强调了对算法内容的详细理解对于正确理解代码含义的重要性。文章包括KMP模式匹配算法的实现代码和性能分析,为读者提供了学习和理解该算法的重要指导。具体内容包括KMP模式匹配算法的实现代码,包括求解next数组和KMP模式匹配算法接口的实现。此外,还介绍了求解next数组的高效新版本代码,并通过图示和分析阐述了如何根据已知的next元素值推导出下一个未知的值。文章内容深入浅出,既有具体的代码实现,又有理论知识的阐述,适合读者快速了解KMP模式匹配算法的核心概念和实现细节。KMP算法的时间复杂度是O(m+n),空间复杂度为O(m)。文章还提供了思考题,引导读者深入思考和互动讨论。整体而言,本文为读者提供了全面而深入的KMP模式匹配算法的学习资料。
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《快速上手 C++ 数据结构与算法》,新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。