/*
* KMP 算法一直以来都是我不好理解的算法之一
* 不好理解主要是有几个考量,这个算法只要我有一段时间不去接触它,我就会遗忘
* 不知道如何再复现这个算法。究其本质原因还是个人对这个算法得理解不深刻
* 最近这段时间,我一直从一个初学者的角度来思考这个算法的本质性的问题
* 我不用画图,一旦使用了图形就意味着理解的程度肯定是上了一个层次,
* 线性的理解方式,是最自然的方式。
*
* KMP算法是在朴素字符串的匹配方法上进行的修正,当子串和主串的某个字符匹配失败后,
* 子串的游标回退到0("当前游标的位置-刚刚匹配的字符数"),主串的游标回退到当前"游标的位置-刚刚匹配的字符数+1"的位置上。
* 如果不理解这个过程,你可以简单的编写一个朴素的算法,我相信这个算法大部分的人都
* 能理解,因为他是线性思维思考的算法
*
* KMP针对的算法就是主串游标的回退的问题!从上面的公式中我们会发现,我们很关心"刚刚匹配的字符数",
* 这也是KMP算法要解决的核心问题,我们KMP算法中的NEXT表的作用就是为这个服务的。
* NEXT表的计算使用子串的性质,这里,我们关心子串中到底有没有前缀包含的问题。
* 所有围绕KMP算法的核心就是子串中有前缀包含,而朴素算法的回退问题就是前缀包含问题导致的
*
* 先来说一个没有前缀包含的的子串"abcd", 这子串就是一个没有前缀包含的子串
* 对于这个子串来说,我们可以改进它的子串匹配算法。
* 当子串游标为0的时候,子串和主串字符匹配失败,主串游标+1
* 其他情况,当主串和子串字符匹配失败的的时候,子串游标设置为0,主串游标不变
* 从算法中我们看到对于没有前缀包含的情况时候,我们不会需要什么NEXT表,也可以实现类似的KMP算法
* 从后面的NEXT表的构建过程中,上述算法只是KMP算法的特例
*
* 含有前缀包含的子串"abcabcacab", 这是一个含有前缀包含的子串
* 这也是我们的主要研究对象,其中最长的前缀包含是"abca"
* abc-abca-cab
* abca-bcacab
* 我们之所以考虑最长的前缀子串是因为,我们只关心匹配失败的时候会出现的情况,最长前缀之后的第一个字符就是匹配失败的字符
* 针对这个位置,我们的跳转位置就是我们关心的,假设字符从0开始计数,我们知道NEXT[7] = 4。
* 还有两个位置需要我们考虑:
* 第一个位置:第一个匹配的字符成功的时候,我们的NEXT的对应值应该是一个特殊的值,这里使用-1,-1表示主串的游标需要加1,子串的游标设置为0
* 第二个位置:前缀匹配上的其他字符的NEXT值的问题,这里我们设置NEXT值为0
* 算法中还有一种CASE需要考虑,如果第一个前缀的第一个字符匹配失败了,NEXT值为多少,这里我们设置NEXT值为0,这是没有前缀包含的时候的情况
*
* 依据上述的算法,我们知道NEXT表的值为:-1,0,0,-1,0,0,0,4,-1,0
*
* 说实在话,说了这么多自己还是一知半解,如果有更好的理解方式,我希望我可以改进
*
* 计算机的算法不应该只能被少数人理解,它是一种做事的方法,这个方法应该尽可能的通俗(线性逻辑算法)
*
* */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
/*
* 这个编码形式不是最简的
void
CalNEXT(const char * T, int * NEXT, int T_L)
{
int i;
int j;
NEXT[0] = -1;
i = 1;
j = 0;
while (i < T_L) {
if (j == 0) {
if (T[i] == T[j]) {
NEXT[i] = -1;
++i;
++j;
} else {
NEXT[i] = 0;
++i;
j = 0;
}
} else if (T[i] == T[j]) {
NEXT[i] = 0;
++i;
++j;
} else {
NEXT[i] = j;
++i;
j = 0;
}
}
} */
void
CalNEXT(const char * T, int * NEXT, int T_L)
{
int i;
int j;
NEXT[0] = -1;
i = 1;
j = 0;
while (i < T_L) {
if (T[i] == T[j]) {
NEXT[i] = (j==0 ? -1 : 0);
++i;
++j;
} else {
NEXT[i] = j;
++i;
j = 0;
}
}
}
int
KMP_GetStrIndex(const char * S, const char * T)
{
int S_L = strlen(S);
int T_L = strlen(T);
int i;
int j;
int * NEXT = (int *)malloc(sizeof(int) * T_L);
CalNEXT(T, NEXT, T_L);
i = 0;
j = 0;
while (i < S_L && j < T_L) {
if (S[i] == T[j]) {
++i;
++j;
} else {
j = NEXT[j];
if (j == -1) {
++i;
j = 0;
}
}
}
return j == T_L ? i-j : -1;
}
int
main(int argc, char ** argv)
{
char main_str[] = "abaacabcabcabcacababc";
char child_str[] = "abcabcacab";
int nIndex; // child_str 在 main_str中的索引值,-1表示不再主串中
nIndex = KMP_GetStrIndex(main_str, child_str);
printf("%d\n", nIndex);
exit(0);
}
KMP算法总结
最新推荐文章于 2023-01-23 18:57:44 发布