此页面记录我在学习数据结构时遇到的一些难点

kmp算法

吐槽:好好好，kmp考纲不参考《算法笔记》，反而按照国内自己的教材，真麻烦

1
2
3
4
5
6
7
8
9
10
11
12
void kmp(string s){
	int i,k=0;
	next[0]=0;
	for(i=1;i<s.size();i++){
		while(k>0 && s[i]!=s[k])k=next[k-1];
		if(s[i]==s[k])k++;
		next[i]=k;
	}
	for(i=0;i<s.size();i++){
		printf("%d",next[i]);
	}
}

手动求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
2
3
if(T[j]==T[next[j]])
    nextval[j]=nextval[next[j]];
else nextval[j]=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) 还要取整