【数据结构 - 串 - KMP算法】next数组的推导【C语言】

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【数据结构 - 串 - KMP算法】next数组的推导【C语言】，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3956字，纯文字阅读大概需要6分钟。

内容图文

KMP算法中，当主串字符s[i]不等于子串字符t[j]时，希望知道s[i]接下来与子串哪个字符比较

---

目录

• • 1 假设
  • 2 推导
  • 3 next数组的定义
  • 4 解释
  • 5 代码实现
  • 6 例子
  • 7 补充
  • 8 参考文献

---

1 假设

• 主串S：‘s[1]s[2]…s[n]’
• 子串T：‘t[1]t[2]…t[m]’
• 一般地，n>=m

2 推导

• 已有部分匹配结果：

  's[i-j+1]s[i-j+2]...s[i-1]' = 't[1]t[2]...t[j-1]'

• 则必有

  's[i-k+1]s[i-k+2]...s[i-1]'='t[j-k+1]t[j-k+2]...t[j-1]'

• 当s[i]不等于t[j]时，子串T需要向右移动，假设此时s[i]应该与t[k]继续比较，k<j

• 则有新的部分匹配结果：

  's[i-k+1]s[i-k+2]...s[i-1]'='t[1]t[2]...t[k-1]'

  且不存在k’<k满足

  's[i-k'+1]s[i-k'+2]...s[i-1]'='t[1]t[2]...t[k'-1]'

• 综合上述等式有：

  't[1]t[2]...t[k-1]' = 't[j-k+1]t[j-k+2]...t[j-1]'
  

• 若next[j]=k表示：当子串第j个字符与主串第i个字符不相等时，应该用子串第k个字符接着与主串第i个字符比较

  • 需要向右移动j-k个字符距离

• 则有next数组的定义

3 next数组的定义

next[j] =
	- 0		当j=1时
	- max{k | 1<k<j，且't[1]t[2]...t[k-1]'='t[j-k+1]t[j-k+2]...t[j-1]'}	当此集合不空时
	- 1		当其他情况时

即

4 解释

• 1<=k<j
• 1<=j<=m
  
  
• j=1时，不存在k，使得k<j，因此，next[j]=0，表示没有字符
• j>1时，
  • 若j=2，显然有k=1
  • 若j>2，则考虑部分匹配结果，取满足定义中等式的最大的k，可能的k值：j-1、j-2、…、1、0
    
    
  • 又k=0，表示找不到满足定义中等式的k，因此，next[j]=1，归入其他情况
  • 又k=1，表示子串第1个字符与主串第i个字符比较，意义特殊，单独列出，归入其他情况
    
    
• 区分：作为字符位置的k、表示不存在的k(即k=0)

5 代码实现

说明：

• 由next数组的定义，用递推的方法有：
• 显然，next[1]=0
• 设next[j]=k，则有：‘t[1]t[2]…t[k-1]’=‘t[j-k+1]t[j-k+2]…t[j-1]’
• 对next[j+1]，子串T对子串T进行模式匹配，
  • 若t[k]==t[j]，则有：‘t[1]t[2]…t[k]’=‘t[j-k+1]t[j-k+2]…t[j]’，于是next[j+1]=k+1
  • 若t[k]不等于t[j]，则考虑next[k]=k’，显然，1<k’<k<j
    • 若t[k’]==t[j]，则next[j+1]=k’+1
    • 若t[k’]不等于t[j]，则…，以此类推
  • 直到不存在k’来参与比较时，认为k’=0，从而有next[j+1]=0+1=1，表示子串第1个字符与主串第i个字符比较

代码：

//函数名：get_next
//功能：求next数组的值
Status get_next(SString T, int next[])
{
    int j = 1;
    int k = 0;
    
    //初值
    next[1] = 0;
    
	//j的范围：1<=j<=T[0]
    while (j < T[0])
    {
        //若k=0，表示找不到k，next[j+1]=1，因此，j和k都需要往下移一位
        //若T[j]==T[k]，next[j+1]=k+1，因此，j和k都需要往下移一位
        if (k==0 || T[j]==T[k])
        {
            ++j;
            ++k;
            next[j] = k;
        }
        else
        {
            //若T[j]不等于T[k]，则考虑next[k]=k' 
            k = next[k];
        }
    }
    
    return OK;
}

6 例子

• 理论结果：
  
• 运行结果：
  

7 补充

• next数组仍可以改进：

  • 当子串T中出现【连续多个相同字符】时，若s[i]与t[j]不相等，而next[j]=k，t[j]==s[k]，从而s[i]与t[k]没有必要再比较
  • 则有nextval数组

• nextval数组

说明：

• 由next数组的定义，用递推的方法有：
• 显然，next[1]=0
• 设next[j]=k，则有：‘t[1]t[2]…t[k-1]’=‘t[j-k+1]t[j-k+2]…t[j-1]’
• 对next[j+1]，子串T对子串T进行模式匹配，
  • 若t[k]==t[j]，则有：‘t[1]t[2]…t[k]’=‘t[j-k+1]t[j-k+2]…t[j]’，于是next[j+1]=k+1
  • 若t[k]不等于t[j]，则考虑next[k]=k’，显然，1<k’<k<j
    • 若t[k’]==t[j]，则next[j+1]=k’+1
    • 若t[k’]不等于t[j]，则…，以此类推
  • 直到不存在k’来参与比较时，认为k’=0，从而有next[j+1]=0+1=1，表示子串第1个字符与主串第i个字符比较
  • 当t[k]==t[j]时，nextval[j+1]=k+1
    • 对子串T，若t[j+1]
      ? ==t[ nextval[j+1] ]
      ? ==t[ nextval[ nextval[j+1] ] ]
      ? ==…，以此类推
    • 找到最小的k’，使得t[j+1]不等于t[k’]，从而nextval[j+1]=nextval[ nextval[j+1] ]=…=k’
    • 若找不到这样的k’，则令k’=0，从而nextval[j+1]=nextval[ nextval[j+1] ]=…=0，表示找不到

//函数名：get_nextval
//功能：求nextval数组的值
Status get_nextval(SString T, int nextval[])
{
    int j = 1;
    int k = 0;
    
    //初值
    nextval[1] = 0;
    
	//j的范围：1<=j<=T[0]
    while (j < T[0])
    {
		//若k=0，表示找不到k，next[j+1]=1，因此，j和k都需要往下移一位
        //若T[j]==T[k]，next[j+1]=k+1，因此，j和k都需要往下移一位
        if (k==0 || T[j]==T[k])
        {
            ++j;
            ++k;
            
            if (T[j] != T[k])
            	nextval[j] = k;
            else
            	//因为从nextval[1]开始就一直取最小的k， 
				//	所以这里去找上一个k，即nextval[k]，就是要找的k' 
            	nextval[j] = nextval[k];
        }
        else
        {
            //若T[j]不等于T[k]，则考虑next[k]=k'
            k = nextval[k];
        }
    }
    
    return OK;
}

运行结果：

• 如果考试的时候，让求字符串“abcaabbabcabaacbacba”的next数组值和nextval数组值，怎么快速求出来？【结果如下】
  

---

8 参考文献

• 严蔚敏, 吴伟民. 数据结构(C语言版)[M]. 北京: 清华大学出版社, 2007.

---

补充：
水平不高，可能还有做得不够好的地方，
希望能和大家交流学习，
转载请注明出处。

内容总结

以上是互联网集市为您收集整理的【数据结构 - 串 - KMP算法】next数组的推导【C语言】全部内容，希望文章能够帮你解决【数据结构 - 串 - KMP算法】next数组的推导【C语言】所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---