[数据结构与算法] 汇总-notes（考试记忆版）_数据结构与算法notes

串

KMP

KMP笔记链接

【例题】模式串"ababaaababaa"，求nextval数组（下标从1开始，0记录长度）

【先求next数组】

1. 先画出表格（下标、T、next），并赋值特殊情况next[1]=0
2. 看下标j那列，记下前面的子串T[1]-T[j-1]，找出最长的前后缀
   1. 没有相同的前后缀 --> next[j] = 1
   2. 有相同的前后缀 --> 取最长的前后缀，长度为len --> next[j]=len+1

【再求nextval数组】

1. 画出nextval行，并赋值特殊情况nextval[1]=0
2. 【算法：求单元格(j, nextval)】先锁定下标为j的那一列 --> 然后看第j列，next那一行（j, next）的值t --> 然后看第t列，T那一行（t, T）–> 用(t, T)和(j, T)比较
   1. (t, T)==(j, T) 的话：(j, nextval)=(t, nextval)
   2. (t, T)≠(j, T)的话：(j, nextval)=(j, next)
3. 【举例：求单元格(5,nextval)】锁定下标为5的那一列 --