数据结构串的kmpnext
时间: 2023-11-26 14:43:13 浏览: 90
数据结构的串
数据结构串的kmpnext是用来求解KMP算法中的next数组的。next数组存储的是模式串中每个字符前的字符串的最长相等前后缀的长度。具体求解过程如下:
1. 初始化j为0,k为-1,即next = -1。
2. 通过循环,计算出next数组的每个值:
- 如果k等于-1或者t.data[j]等于t.data[k],则令j和k分别增加1,同时将next[j]的值赋值为k。
- 否则,令k的值等于next[k],即回退到前一个字符处继续比较。
3. 重复步骤2直到j等于模式串的长度减1。
举个例子,假设模式串t为"abcabcmn",那么求得的next数组为:next=-1, next=0, next=0, next=0, next=1, next=2, next=3, next=0。
阅读全文