此页面记录我在学习数据结构时遇到的一些难点
kmp算法
吐槽:好好好,kmp考纲不参考《算法笔记》,反而按照国内自己的教材,真麻烦
1 | void kmp(string s){ |
手动求nextval数组(模式串下标从1开始)
若在KMP算法设计中,将模式串下标从1开始计数,那么求nextval数组的算法步骤为:
(1)求出next数组的值(定义next[1]=0,next[2]=1);
(2)定义nextval[1]=0。然后,比较模式串的第j个(j>1)字符是否与第next[j]个字符相等。若相等,则模式串第j个字符的nextval值等于第next[j]个字符的nextval值。若不等,则模式串第j个字符的nextval值等于其next数组值。
1 | if(T[j]==T[next[j]]) |
手动求nextval数组(模式串下标从0开始)
若在KMP算法设计中,将模式串下标从0开始计数,那么求nextval数组的算法步骤为:
(1)求出next数组的值(定义next[0]=-1,next[1]=0);
(2)定义nextval[0]=-1。然后,比较模式串的第j个(j>0)字符是否与第next[j]个字符相等。若相等,则模式串第j个字符的nextval值等于第next[j]个字符的nextval值。若不等,则模式串第j个字符的nextval值等于其next数组值。
树
(1)树中的结点数等于所有结点的的度数之和加1
(2)度为m的树中第i层上至多有m^(i-1)个结点(i>=1)
(3)高度为h的m叉树至多有(m^h-1)/(m-1)个结点
(4)具有n个结点的m叉树的最小高度为logm(n(m-1)+1) 还要取整
文章作者: Ldyer
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Ldyer!
评论