kmp算法中abababababba的next数组
时间: 2023-11-19 08:53:43 浏览: 59
KMP算法中"abababababba"的next数组为:0 0 1 2 3 4 5 6 7 8 0。具体计算过程如下:
首先,第一位和第二位的next值分别为0,1。
然后,计算第三位(即下标为2的数据'b')的next值,因为前两位已经确定,所以只需要比较第一位和第二位是否相等即可,因为不相等,所以next=0。
接着,计算第四位(即下标为3的数据'a')的next值,因为前三位已经确定,所以只需要比较第一位和第三位是否相等即可,因为不相等,所以next=0。
然后,计算第五位(即下标为4的数据'b')的next值,因为前四位已经确定,所以只需要比较第一位和第四位是否相等即可,因为相等,所以next=1。
接着,计算第六位(即下标为5的数据'a')的next值,因为前五位已经确定,所以只需要比较第一位和第五位是否相等即可,因为不相等,所以next=0。
然后,计算第七位(即下标为6的数据'b')的next值,因为前六位已经确定,所以只需要比较第一位和第六位是否相等即可,因为相等,所以next=1。
接着,计算第八位(即下标为7的数据'a')的next值,因为前七位已经确定,所以只需要比较第一位和第七位是否相等即可,因为不相等,所以next=0。
然后,计算第九位(即下标为8的数据'b')的next值,因为前八位已经确定,所以只需要比较第一位和第八位是否相等即可,因为相等,所以next=1。
接着,计算第十位(即下标为9的数据'a')的next值,因为前九位已经确定,所以只需要比较第一位和第九位是否相等即可,因为不相等,所以next=0。
最后,计算第十一位(即下标为10的数据'b')的next值,因为前十位已经确定,所以只需要比较第一位和第十位是否相等即可,因为相等,所以next[10]=1。
最后一位的next值为0,因为它没有真前缀和真后缀。