KMP模式匹配一直匹配位置都是0

Question

请各位帮忙看一下，KMP模式匹配这一块，输出的位置下标为什么一直是0。

//计算next修正数组值
void get_nextval(SqString t,int nextval[])
{
    int i = 1;    //待计算的串位置
    int j = 0;    //被比较的串位置
    nextval[1] = 0;
    
    while (i < t.length)
    {
        if (j == 0 || t.data[i] == t.data[j])    //匹配成功或被比较的串位置值为0
        {
            ++i;
            ++j;
            
            if (t.data[i] != t.data[j])            
            {
                nextval[i] = j;
            }
            else
                nextval[i] = nextval[j];        
        }
        else            //匹配失败 i不变，j继续指向下一个nextval值
        {
            j = nextval[j];
        }
    }
}

//KMP算法
//返回模式T在主串s中第pos个字符开始第一次出现的位置。若不存在， 则返回值为0 
int Index_KMP(SqString s, SqString t,int pos)
{
    int i = pos;    //主串起始位置
    int j = 1;        //模式串起始位置
    
    while (i<=s.length && j<=t.length)
    {
        if (j == 0 || s.data[i] == t.data[j])    //若相等或子串位j等于0 主串子串都往后移一位然后继续 ,(在BF算法中没有j等于0的情况)
        {
            ++i;
            ++j;
        }
        else                    //不相等 子串j按照next数组移动，主串i不回溯
        {
            j = nextval[j];
        }
    }
    if (j >= t.length) return i-t.length;    //匹配成功
    else return 0;                            //匹配失败
}

这里本意是写一个简单的文本替换，想看一下KMP模式匹配写对了没有，就尝试输出匹配的位置下标，结果都一直是0，看了一些其他人的KMP，写法都一样，实在是不知道错哪了？
如果需要完整代码修改，我可以提供。

Answer 1

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7525206
• 你也可以参考下这篇文章：简单模式匹配算法和KMP算法
• 除此之外, 这篇博客: 模式匹配：暴力匹配（BF），快速匹配（KMP）中的 模式匹配： 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:
  

  1.暴力匹配(BF)：模式串和主串，从头开始匹配，如果遇到不匹配，则从头开始重新匹配，主串返回到原来起始位置向后移动一位。
  
  然后一直查找直到最后找到
  最后匹配成功，将匹配成功后的剩余主串返回，并且输出。其匹配成功的下标应该为i-j ;
  其适用范围为模式串中的重复字符较少的情况，时间复杂度较高，为O(m*n),m为字串长度，n为主串长度,空间复杂度较低为O(1)。

  //暴力匹配 ，时间复杂度O(m*n)m为子串长度，n为主串长度 BF
  char *my_strstr1(char *string, const char *strCharSet)
  {
  	assert(string != NULL && strCharSet != NULL);
  	char *pdest = string;
  	const char *psrc = strCharSet;
  	int i, j;
  	i = j = 0;
  	while (pdest[i] != '\0'&& psrc[j] != '\0')
  	{
  		if (pdest[i]==psrc[j])
  		{
  			i++;
  			j++;
  		}
  		else{
  			i = i - j + 1;
  			j = 0;
  		}
  	}
  	if (psrc[j] == '\0')
  		return string + i - j; 
  	else
  		return NULL;
  }
  int main()
  {
  	char s[] = "abababababaaaabababc";
  	char t[] = "abababc";
  	char *ar=my_strstr(s, t);
  	printf(" s = %s\n", ar);
  	system("pause");
  	return 0;
  }
  

  2.快速匹配(KMP):
   对于暴力算法，如果出现不匹配字符，同时回退 主串和模式串的指针，嵌套 循环，时间复杂度 O(MN)，空间复杂度 O(1)。
   KMP相对于暴力匹配来说时间复杂度大大降低，只需要O(m+n),
   对于KMP算法来说最主要的还是next 数组的实现。
   不说了，老表上图。
  

  

  下面的规律根据上面前后缀的最长相等长度很容易得到
  
  写出next数组代码为：

  void Next(char *pdest, int *next)
  {
  	int len = strlen(pdest);
  	next[0] = 0;
  	int j = 0;
  	for (int i = 1; i < len; ++i)
  	{                                                  
  		while (j>0 && pdest[j] != pdest[i])
  			j = next[j - 1];
  		if (pdest[j] == pdest[i])
  			j++;
  		next[i] = j;
  	}
  }
  

  得到了next 数组，老表们就可以根据next数组来进行匹配了，咱们接着上图，
  主串与模式串进行匹配，主要不同于BF的方面为，主串指针不回说，当匹配不当时，只移动模式串指针。
  当模式串与主串不匹配时，模式串指针根据next数组，进行回溯，
  其指针回溯到其前一个next数组的值， 再此进行匹配，直到循环结束，

  在这里插入代码片	while (pdest[i] != '\0' && psrc[j] != '\0')
  	{
  		if (pdest[i] == psrc[j])
  		{
  			i++;
  			j++;
  		}
  		else{
  			j = next[j-1];
  		}
  	}
  

  循环有两个出口，判断其出口到底是匹配成功还是失败，成功就将后面的字符串返回，失败则返回-1.
  最后，给大家附上KMP总代码

  #include<stdio.h>
  #include<windows.h>
  #include<assert.h>
  #include<string.h>
  #include<stdbool.h>
  #pragma warning(disable:4996)
  void Next(char *pdest, int *next)
  {
  	int len = strlen(pdest);
  	next[0] = 0;
  	int j = 0;
  	for (int i = 1; i < len; ++i)
  	{                                                  
  		while (j>0 && pdest[j] != pdest[i])
  			j = next[j - 1];
  		if (pdest[j] == pdest[i])
  			j++;
  		next[i] = j;
  	}
  }
  char *my_strstr2(char *string, char *strCharstring)
  {
  	assert(string != NULL && strCharstring != NULL);
  	char *pdest = string;
  	char *psrc = strCharstring;
  	int next[7];
  	Next(psrc, next);
  	int i, j;
  	i = j = 0;
  	while (pdest[i] != '\0' && psrc[j] != '\0')
  	{
  		if (pdest[i] == psrc[j])
  		{
  			i++;
  			j++;
  		}
  		else{
  			j = next[j-1];
  		}
  	}
  	if (psrc[j] == '\0')
  		return string + i - j;
  	else
  		return NULL;
  }
  int main()
  {
  	char s[] = "abababababaaaabababcccccc";
  	char t[] = "abababc";
  	char *ar = my_strstr2(s, t);
  	printf(" s = %s\n", ar);
  	system("pause");
  	return 0;
  }
  

  欢迎大家指点。

• 您还可以看一下 孙玖祥老师的图解数据结构与算法课程中的 KMP算法思想-动画演示小节, 巩固相关知识点
  

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^