字符串匹配之KMP算法(续)---还原next数组

时间:2023-03-09 02:54:32
字符串匹配之KMP算法(续)---还原next数组

相信通过今天的文章,你会对KMP的认识更加深入一层,不止停留在知道怎样计算的层面上了,废话不多说,開始。

通过前面的第一篇文章,知道了怎么求next数组,相信非常多喜欢刨根问底的人就会问,我依照你的做法确实可以解决问题,那么next数组究竟是个神马东西喃?为啥会那样求喃?

next数组为啥那样求?今天翻阅算法导论发现有证明next数组迭代计算的正确性,可以理解点,可是还不到可以写出来的程度,又把july的文章大致浏览下,想看看他是怎么介绍的,发现他把这部分也略过了,在文章最后说用了1年的时间才全然明确理解。看看如今的我,也还是处于尚未全然理解的程度,所以这部分(next数组的计算原因)决定暂且放下不写,释怀一段时间(预计会非常长,由于接下来时间会非常紧)后有精力再学习的时候加上。

     所以今天就说说,next数组究竟是个神马东西?
     本篇文章以 阮一峰 那篇文章的最后一部分開始,假设你不了解KMP或没看过我的第一篇KMP的文章,那最好先花5到10分钟先阅读也算是预热一下。
一、以"ABCDABD"为例,来了解下前缀,后缀:
  - "A"的前缀和后缀都为空集,共同拥有元素的长度为0;
  - "AB"的前缀为[A],后缀为[B],共同拥有元素的长度为0;
  - "ABC"的前缀为[A, AB],后缀为[BC, C],共同拥有元素的长度0;
  - "ABCD"的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共同拥有元素的长度为0;
  - "ABCDA"的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共同拥有元素为"A",长度为1;
  - "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共同拥有元素为"AB",长度为2;
  - "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共同拥有元素的长度为0。

、next数组存储的是 模式串中 之前已经匹配的字符 的"前缀"和"后缀"的 最长的 共同拥有元素 的长度
     概念比較绕,注意我上面句子中使用了空格来帮助你理解,以下举个样例说下, 有模式串 T = "ABCDABD"
    字符串匹配之KMP算法(续)---还原next数组字符串匹配之KMP算法(续)---还原next数组
     在求next[j] 时候,我们如果T[0]--T[j-1]都可以匹配成功,这个如果是合理的,由于仅仅有每次匹配失败的时候才会使用next数组来获得下一次匹配開始的位置。
     上面的话 请多读几遍。
     好,我们来求next[1], 模式串中之前已经匹配的字符是T[0]= A, 在第一部分讲过他的前缀后缀都为空,共同拥有元素长度为 0 ,所以next[1]=0;
     求next[4], 模式串中之前已经匹配的字符是T[0]--T[3]={A, B, C, D}, 从第一部分得到他的前缀和后缀共同拥有元素长度为0,所以next[4] = 0;
     求next[5], 模式串中之前已经匹配的字符是T[0]--T[4]={A, B, C,D, A}, 从第一部分得到他的前缀和后缀共同拥有元素为'A', 长度为1, 所以next[5]=1;
     好了,其它的几个自己试着来推倒推倒。

三、next数组的还有一理解(对于学习后面的BM算法做一点点小小的铺垫)
     如果有一例如以下的匹配
字符串匹配之KMP算法(续)---还原next数组
     留意我图上颜色的两个AB,在D匹配失败的时候,next数组事实上做的就是让前面的AB移动到后面匹配的AB,例如以下图:
字符串匹配之KMP算法(续)---还原next数组
     这样来避免回溯,加快效率的。在我后面打算要介绍的BM算法中这样的出现的字符串叫做好字符串,哈哈,是不是又长知识了,好了,今天的介绍就到这里为止,这样KMP就算介绍完了。


假设你认为本篇对你有收获,请帮顶。

另外,我本人开通了微信公众号--分享技术之美,我会不定期的分享一些我学习的东西.
你能够搜索公众号:swalge 或者扫描下方二维码关注我
字符串匹配之KMP算法(续)---还原next数组
(转载文章请注明出处: http://blog.csdn.net/swagle/article/details/24112823
)