串的net数组值求法与netval求法.doc

《串的net数组值求法与netval求法.doc》由会员分享，可在线阅读，更多相关《串的net数组值求法与netval求法.doc（7页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、记得大学时自己也总结出了这种算法的，手动计算，数据构造的书都丢了，还好在网上找会了同样的算法特记下：int get_nextval(SString T,int &nextval ) /求模式串T的next函数修正值并存入数组nextval。 i=1; nextval1=0; j=0; while(iT0) if(j=0|Ti=Tj) +i;+j; if (Ti!=Tj) nextvali=j; else nextvali=nextvalj; else j=nextvalj; /get_nextval 根据这段程序来求nextval的值是可以方便计算出来，但如果是应付考研试题或者期末考试就有点麻

2、烦了。而如果记住我推荐的方法，那么任何时候都可以很方便地求解nextval了。 首先看看next数组值的求解方法。 例如： 模式串 a b a a b c a c next值 0 1 1 2 2 3 1 2 nextval值 next数组的求解方法是：第一位的next值为0，第二位的next值为1，后面求解每一位的next值时，根据前一位进展比拟。首先将前一位与其next值对应的内容进展比拟，如果相等，那么该位的next值就是前一位的next值加上1；如果不等，向前继续寻找next值对应的内容来与前一位进展比拟，直到找到某个位上内容的next值对应的内容与前一位相等为止，那么这个位对应的值加上

3、1即为需求的next值；如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。 看起来很令人费解，利用上面的例子具体运算一遍。 1.前两位必定为0与1。 2.计算第三位的时候，看第二位b的next值，为1，那么把b与1对应的a进展比拟，不同，那么第三位a的next的值为1，因为一直比到最前一位，都没有发生比拟一样的现象。 3.计算第四位的时候，看第三位a的next值，为1，那么把a与1对应的a进展比拟，一样，那么第四位a的next的值为第三位a的next值加上1。为2。因为是在第三位实现了其next值对应的值与第三位的值一样。 4.计算第五位的时候，看第四位a的next

4、值，为2，那么把a与2对应的b进展比拟，不同，那么再将b对应的next值1对应的a与第四位的a进展比拟，一样，那么第五位的next值为第二位b的next值加上1，为2。因为是在第二位实现了其next值对应的值与第四位的值一样。 5.计算第六位的时候，看第五位b的next值，为2，那么把b与2对应的b进展比拟，一样，那么第六位c的next值为第五位b的next值加上1，为3，因为是在第五位实现了其next值对应的值与第五位一样。 6.计算第七位的时候，看第六位c的next值，为3，那么把c与3对应的a进展比拟，不同，那么再把第3位a的next值1对应的a与第六位c比拟，仍然不同，那么第七位的ne

5、xt值为1。 7.计算第八位的时候，看第七位a的next值，为1，那么把a与1对应的a进展比拟，一样，那么第八位c的next值为第七位a的next值加上1，为2，因为是在第七位与实现了其next值对应的值与第七位一样。 在计算nextval之前要先弄明白，nextval是为了弥补next函数在某些情况下的缺陷而产生的，例如主串为“aaabaaaab、模式串为“aaaab那么，比拟的时候就会发生一些浪费的情况：比拟到主串以及模式串的第四位时，发现其值并不相等，据我们观察，我们可以直接从主串的第五位开场与模式串进展比拟，而事实上，却进展了几次多余的比拟。使用nextval可以去除那些不必要的比拟次

6、数。 求nextval数组值有两种方法，一种是不依赖next数组值直接用观察法求得，一种方法是根据next数组值进展推理，两种方法均可使用，视更喜欢哪种方法而定。 我们使用例子“aaaab来考察第一种方法。 1.试想，在进展模式匹配的过程中，将模式串“aaaab与主串进展匹配的时候，如果第一位就没有吻合，即第一位就不是a，那么不用比拟了，赶快挪到主串的下一位继续与模式串的第一位进展比拟吧，这时，模式串并没有发生偏移，那么，模式串第一位a的nextval值为0。 2.如果在匹配过程中，到第二位才发生不匹配现象，那么主串的第一位必定是a，而第二位必定不为a，既然知道第二位一定不为a，那么主串的第一

7、、二两位就没有再进展比拟的必要，直接跳到第三位来与模式串的第一位进展比拟吧，同样，模式串也没有发生偏移，第二位的nextval值仍然为0。 3.第三位、第四位类似2的过程，均为0。 4.如果在匹配过程中，直到第五位才发生不匹配现象，那么主串的第一位到第四位必定为a，并且第五位必定不为b，可是第五位仍然有可能等于a。如果万一第五位为a，那么既然前面四位均为a，所以，只要第六位为b，第一个字符串就匹配成功了。所以，现在的情况下，就是看第五位终究是不是a了。所以发生了下面的比拟： 1 2 3 4 5 6 a a a a * * a a a a b a a a a b 前面的三个a都不需要进展比拟，只

8、要确定主串中不等于b的那个位是否为a，即可以进展如下的比拟：如果为a，那么继续比拟主串后面一位是否为b；如果不为a，那么此次比拟完毕，继续将模式串的第一位去与主串的下一位进展比拟。由此看来，在模式串的第五位上，进展的比拟偏移了4位不进展偏移，直接比拟下一位为0，故第五位b的nextval值为4。 我们可以利用第一个例子“abaabcac对这种方法进展验证。 a的nextval值为0，因为如果主串的第一位不是a，那么没有再比拟下去的必要，直接比拟主串的第二位是否为a。如果比拟到主串的第二位才发生错误，那么主串第一位肯定为a，第二位肯定不为b，此时不能直接跳到第三位进展比拟，因为第二位还可能是a，

9、所以对主串的第二位再进展一次比拟，偏移了1位，故模式串第二位的nextval值为1。以此类推，nextval值分别为：01021302。其中第六位的nextval之所以为3，是因为，如果主串比拟到第六位才发生不匹配现象，那么主串的前五位必定为“abaab且第六位必定不是“c，但第六位如果为“a的话，那么我们就可以从模式串的第四位继续比拟下去。所以，这次比拟为： 1 2 3 4 5 6 7 8 9 10 11 12 a b a a b * * * * * * * a b a a b c a c 而不是： 1 2 3 4 5 6 7 8 9 10 11 12 a b a a b * * * * *

10、 * * a b a a b c a 因为前两位a与b已经确定了，所以不需要再进展比拟了。所以模式串第六位的nextval值为这次比拟的偏移量3。 再来看求nextval数组值的第二种方法。模式串 a b a a b c a c next值 0 1 1 2 2 3 1 2 nextval值 0 1 0 2 1 3 0 2 1.第一位的nextval值必定为0，第二位如果于第一位一样那么为0，如果不同那么为1。 2.第三位的next值为1，那么将第三位与第一位进展比拟，均为a，一样，那么，第三位的nextval值为0。 3.第四位的next值为2，那么将第四位与第二位进展比拟，不同，那么第四位的

11、nextval值为其next值，为2。 4.第五位的next值为2，那么将第五位与第二位进展比拟，一样，第二位的next值为1，那么继续将第二位与第一位进展比拟，不同，那么第五位的nextval值为第二位的next值，为1。 5.第六位的next值为3，那么将第六位与第三位进展比拟，不同，那么第六位的nextval值为其next值，为3。 6.第七位的next值为1，那么将第七位与第一位进展比拟，一样，那么第七位的nextval值为0。 7.第八位的next值为2，那么将第八位与第二位进展比拟，不同，那么第八位的nextval值为其next值，为2。 在“aaaab内进展验证。 模式串 a a a a b next值 0 1 2 3 4 nextval值 0 0 0 0 4 第 7 页