KMP算法

next和nextval求解方法

next数组求解过程:首先确定next数组的前两位一定是0和1,然后从j = 3 开始计算
j = 3 前面的字符串 ab没有相同前后缀 next[3] = 1
j = 4 前面的字符串 aba有相同前后缀a 长度为1 next[4] = 1 + 1 = 2
j = 5 前面的字符串 abaa有相同前后缀a 长度为1 next[5] = 1 + 1 = 2
j = 6 前面的字符串 abaab有相同前后缀ab 长度为2 next[6] = 1 + 2 = 3
j = 7 前面的字符串 abaabc没有相同前后缀 next[7] = 1
j = 8 前面的字符串 abaabca有相同的前后缀a 长度为1 next[8] = 1 + 1 = 2

nextval数组求解过程:首先确定nextval数组的第一位一定是0,然后从j = 2 开始计算
j = 2 next[2] = 1 与 j = 1 的元素比较因为b != a nextval[2] = next[2] = 1
j = 3 next[3] = 1 与 j = 1 的元素比较因为a == a nextval[3] = nextval[1] = 0
j = 4 next[4] = 2 与 j = 2 的元素比较因为a != b nextval[4] = next[4] = 2
j = 5 next[5] = 2 与 j = 2 的元素比较因为b == b nextval[5] = nextval[2] = 1
j = 6 next[6] = 3 与 j = 3 的元素比较因为c != a nextval[6] = next[6] = 3
j = 7 next[7] = 1 与 j = 1 的元素比较因为a == a nextval[7] = nextval[1] = 0
j = 8 next[8] = 2 与 j = 2 的元素比较因为c != b nextval[8] = next[8] = 2

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。