文章作者:Slyar 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。
这周的数据结构课讲的是串,本以为老师会讲解KMP算法的,谁知到他直接略过了...没办法只能自己研究,这一琢磨就是3天,期间我都有点怀疑自己的智商...不过还好昨天半夜终于想明白了个中缘由,总结一些我认为有助于理解的关键点好了...
书上有的东西我就不说了,那些东西网上一搜一大片,我主要说一下我理解的由前缀函数生成的next数组的含义,先贴出求next数组的方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
void GetNext(char* t, int* next)
{
int i, j, len;
i = 0;
j = -1;
next[0] = -1;
while(t[i] != '/0')
{
if (j == -1 || t[i] == t[j])
{
i++;
j++;
next[i] = j;
}
else
{
j = next[j];
}
}
}
|
当一个字符串以0为起始下标时,next[i]可以描述为"不为自身的最大首尾重复子串长度"。
也就是说,从模式串T[0...i-1]的第一个字符开始截取一段长度为m(m < i-1)子串,再截取模式串T[0...i-1]的最后m个字符作为子串,如果这两个子串相等,则该串就是一个首尾重复子串。我们的目的就是要找出这个最大的m值。
例如:
若 i = 4 ,则 i - 1 = 3 , m = next[4] = 2
从T[0...3]截取长度为2的子串,为"ab"
从T[0..3]截取最后2个字符,为"ab"
此时2个子串相等,则说明 next[4] = 2 成立,也可证明 m = 2 为最大的m值。
本来一开始我是没有加"不为自身"这个限制条件的,可是后来我发现一种情况:
若 i = 4 ,则 i - 1 = 3 , m = next[4] = 3
从T[0...3]截取长度为3的子串,为"aaa"
从T[0..3]截取最后3个字符,为"aaa"
此时2个子串相等,则说明 next[4] = 3 成立。
但是我发现如果next[4] = 4:
从T[0...3]截取长度为4的子串,为"aaaa"
从T[0..3]截取最后4个字符,为"aaaa"
此时2个子串也是相等的,那么是不是说明 next[4] 应该等于4呢?
仔细观察后发现,如果 next[4] = 4 ,那么T[0...3]的前4个字符和后4个字符是重合的,并且重复子串和T[0...3]也是相等的。看过教材后发现教材中给出的前缀函数定义有一句为:next[j] = max{k | 0 < k < j 且 'p[0]...p[k-1]' = 'p[j-k+1]...p[j-1]'},应该不包含子串为本身的情况...
这样再做PKU 2406 和 PKU 1961 的时候就很简单了,用 length - next[length] 求出"不为自身的最大首尾重复子串长度",此时需要多求一位next[length]值,若最大重复子串的长度是length的非1整数倍,则证明字符串具有周期重复性质。
PKU 2752 是求 前缀 == 后缀 的长度,也就是首尾重复子串长度,利用next数组记录的"不为自身的最大首尾重复子串长度"可以马上得到结果。
恩,先说这么多吧,可能有不对的地方,以后理解的更深了再回来改...哪位大牛路过看到错误请指出哈。
相关推荐
字符串匹配算法:穷举、KMP、BM.ppt
KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,由Donald Knuth、Vaughan Pratt和James H. Morris共同发明。KMP算法通过使用一个称为“部分匹配表”或“next数组”的数组来减少字符串匹配过程中的...
KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,由Donald Knuth、Vaughan Pratt和James H. Morris共同发明。KMP算法通过使用一个称为“部分匹配表”或“next数组”的数组来减少字符串匹配过程中的...
KMP字符串匹配算法,一种快速模式匹配算法
带通配符的字符串匹配算法,带通配符的字符串匹配算法
字符串的模式匹配算法——KMP的C++实现。
实现BF算法的改进算法:KMP算法和BM算法; 对上述3个算法进行时间复杂性分析,并设计实验程序验证分析结果。 附件中 3.3.h BF算法代码 3.5.h KMP算法代码 3.12.h BM算法代码
主要讲述字符串模式匹配的KMP算法的基本思想,算法过程。没有进一步细化和改进。
字符串匹配 KMP算法
KMP字符串模式匹配算法ppt,KMP算法是很精妙的算法,同时比较难懂。KMP字符串模式匹配算法ppt
字符串匹配算法理解(从BF算法到KMP算法) 暴风(Brute Force)算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和 T的第二个字符...
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配...
串匹配(String Matching)问题是计算机科学中的一个基本问题,也是复杂性理论中研究的...本章中分别介绍改进的KMP串匹配算法,采用散列技术的随机串匹配算法,基于过滤算法的近似串匹配算法,以及它们的MPI编程实现。
这是字符串匹配算法中很著名的KMP算法,此文件仅供大家参考,具体是否能调通,本人还没有试过
vc++ 带通配符的字符串匹配算法实例源代码,用"*" 和 "?"进行字符串的匹配查找。直接拷贝代码就能使用。部分函数功能:带通配符的字符串匹配 参数:lpszSour是一个普通字符串; lpszMatch是一可以包含通配符的...
包括以下几种字符串匹配算法的C代码实现,谨供参考: 平凡算法(SimpleSM); KMP算法(KMPSM); BM算法(bmSM); RK算法(rkSM);
简单介绍了字符串匹配相关算法,如穷举、KMP、BM,做个大致的了解
kmp高效字符串匹配算法,算法复杂度大大减小。
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的...