855学习记录数据结构杂谈(2)——炎泽汐$de$ Blog

文章目录[隐藏]

• $KMP$算法
• 广义表

$next$数组

---

      $next$数组的实质是一个前缀表，其作用是用来回退，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。具体来说前缀表记录下标$i$之前（包括$i$）的字符串中，有多大长度的相同前缀后缀，即最长公共前后缀。

      文章中字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串；前缀表所记录的就是最长的相同的前后缀的长度。

void getNext(int* next,  char* s){
    int i = 0, j = -1;
    next[0] = j;
    while(i < strlen(s) - 1){
    	if(0 > j || s[i] == s[j]){
    		i++;
    		j++;
    		next[i] = j;
    	}else{
    		j = next[j];
    	}
    }
}

      那么使用 next 数组，用模式串匹配文本串的整体代码如下：

int KMP(int* next, char* P, char* T){
	getNext(next, P);
	int m = strlen(P), n = strlen(T), i = 0, j = 0;
	while(j < m && i < n){
		if(0 > j || T[i] == P[j]){
			i++;
			j++;
		}else{
			j = next[j];
		}
	}
	return i - j;
}

$nextval$数组

---

void getNextval(int* next, char* P){
    int i = 0, j = -1;
    next[0] = j;
    while(i < strlen(P) - 1){
    	if(0 > j || P[i] == P[j]){
    		i++;
		j++;
		next[i] = (P[i] != P[j] ? j : next[j]);
	}else{
		j = next[j];
	}
    }
}

定义与性质

---

      广义表也是一种线性存储结构，既可以存储不可再分的元素，也可以存储广义表，记作：$LS=(a_1,a_2,…,a_n)$，其中，$LS$代表广义表的名称，$a_n$表示广义表存储的数据，广义表中每个$a_i$既可以代表单个元素，也可以代表另一个广义表。

      广义表的长度∶为表中最上层元素的个数。

      广义表的深度∶为表中括号的最大层数。注意，求深度时需要将子表展开。

      表头和表尾∶当广义表非空时，第一个元素为广义表的表头，其余元素组成的表是广义表的表尾。