sppk.net
当前位置:首页 >> 已知一个模式串T="AAABA",则在KMP算法中,其nExt数组中的值是 ( >>

已知一个模式串T="AAABA",则在KMP算法中,其nExt数组中的值是 (

abaabcac01122312 前两个字母next序列分别为01,直接写上 第三个"a" 时,它前一个字母为b,从头开始字母为a, a!=b所以为1 第四个"a" 时,前字母为a,从头开始字母为a,a=a,所以值为1+1=2(相等时为串长加1) 第五个"b",前个字母为a,从头开始a,a=a,为2 第六个"c",前个字母为b,再往前是a,ab,从头开始ab串,ab=ab,因此值为2+1=3 第七个字母为"a",前个字母为c,与从头开始的第一个字母不相等,所以为1 第八个为"c",前个字母为a,与开始第一个字母相等,因此为2 则返回逻辑“真(TRUE)”,反之返回逻辑“假(FALSE)”.

你也是在学数据结构吧,next数组是0 1 2 3

对于next[]数组也就是子串的某个位置与自身的公共前缀的最后匹配位置.这样讲可能有点抽象,说白了就是子串以该位置为最末位,自己和自己匹配的最长公共前缀.而在进行next[]数组的第i个位置的求值时,该位置以前的所有next[]值已经求出

虽然我很聪明,但这么说真的难到我了

1. Next=011223 是对的2. 不一定, 比如 "aaaab" NEXT = 000043. 可能大于3, 例子同2.NEXT的数字大小取决于模式串与自身的"匹配长度".

一个串的next数组,可以这样理解 对于next[i]的值,等于该串0~i-1的这个串中,前几个字符组成的串,与后几个字符完全相同.举个例吧,ababc,next数组下标就是0~4的范围啦~~ 首先next[0]=0,这是肯定的,其实next[0]没意义计算next[

next[i]表示的是:在第i个字符前面的i-1个字符里面,从开头开始的1个字符与最后1个字符是否相等,若不是,则next[i]=0,否则继续看下面;从开头开始的2个字符与最后2个字符是否相等,若不是,则next[i]=1,否则继续看下面;从开头开始的3个字符与最后3个字符是否相等,若不是,则next[i]=2,否则继续看下面;……就是这样的判断取值.它的意思就是如果到了某个字符不匹配的情况时候,你就可以直接把模式串拖到从开头开始的那next[i]个字符等于当前字符的前next[i]个字符的地方,这样就少了很多重复的无效的比较和移动.

计算字符串的next函数值,可以参考"KMP模式匹配算法".计算过程:下标j 1 2 3 4 5 6 7 8 9 10 11 12 字符串 a b a b a a a b a b a a next[j] 0 1 1 2 3 4 2 2 3 4 5 6 1) 当j=1时,固定就是next[1]=0;2) 当j=2时,由1到j-1的字符串是"a",属于其

如果需要考虑到特殊的情况 那么还需要这样修改把你的修改下就是了 public static void GetModeNext(string t, int[] next) {int j; int i=1;next[1]=0;j=0;while(i<t[0]){if(j==0||t[i]==t[j]) {++i;++j; if(t[i]!=t[j])next[i]=j; else next[i]=next[j]; }elsej=next[j];}}

相关文档
网站首页 | 网站地图
All rights reserved Powered by www.sppk.net
copyright ©right 2010-2021。
内容来自网络,如有侵犯请联系客服。zhit325@qq.com