在牛客网刷题遇到了求next数组的题型,结果在学校学的没有牢记,做错了,还是要多刷题做总结啊。
我们先口述说明一下next数组的求解方法:
我们能确定next数组第一二位一定分别为0,1,后面求解每一位的next值时,根据前一位进行比较。 从第三位开始,将前一位与其next值对应的内容进行比较, 如果相等,则该位的next值就是前一位的next值加上1; 如果不等,向前继续寻找next值对应的内容来与前一位进行比较, 直到找到某个位上内容的next值对应的内容与前一位相等为止, 则这个位对应的值加上1即为需求的next值; 如果找到第一位都没有找到与前一位相等的内容,那么求解的位上的next值为1。
下面我们具体看题理解一下:
问题:已知串S= ‘ababaaababaa ’ , 求其 Next 数值序列
解答步骤:
1.next数组第一二位一定分别为0,1:
2.看第三位,按照next数组求解方法。第三位a的前一位是第二位的b,b的next值是1对应内容是a,b与a不同,则继续向前寻找next值对应的内容与第二位的b进行比较。但是找到第一位都没有找到与第二位的b相等的内容,所以第三位a的next值为1,则:
3.看第四位的b,b的前一位a的next值1对应内容为a,相同,所以该位b的next值就是前一位a的next(第三位的a)值加上1,即为2:
4.看第五位a,a的前一位b的next值2对应内容为b,相等,所以第五位a的next值就是其前一位b的next值加上1,即为3:
5.看第六位a,a的前一位a的next值3对应内容为a,相等,所以该位a的next值就是前一位a的next值加上1,即为4:
6.看第七位a,a的前一位a的next值4对应内容为b,不相等,向前继续寻找next值对应的内容来与前一位进行比较,b的next值2对应的内容为b,依旧不相等,继续向前寻找,第二位b的next值1对应内容为a,相等。因为是在第二位b处实现的相等,所以第七位a的next值为第二位b的next值上加1,即为2:
7.看第八位b,b的前一位a的next值2对应内容为b,不相等,向前继续寻找next值对应的内容来与前一位进行比较,b的next值1对应的内容为a,相等。因为是在第二位b处实现的相等,所以第八位a的next值为第二位b的next值上加1,即为2:
8.看第九位,前一位b的next值2对应内容为b,相等,所以此处next值为3:
9.第十位同理上面第8可得,为4:
10.第十一位a的前一位b的next值4对应内容为b,相等,所以此处next值为5:
11.最后,第十二位也是同理可以得到next值位6:
最后我们就求解出来了,该串′ababaaababaa′的next数组为:011234223456
只要我们记住了这个规则,再多的串也是同样的求解方法,希望也能帮助大家。