数据结构第四章-串
计算机学科基础：数据结构第四章串的学习笔记
1.串的定义（特殊的线性表，了解）
- 定义：串是由零个或多个字符组成的有限序列（串的数据对象限定为字符集）
- 串中字符的个数n称为串的长度。n=0时的串称为空串
- 串中任意多个连续的字符组成的子序列称为该串的子串，包含子串的串称为主串。（以子串作为操作对象）
- 某个字符在串中的序号称为该字符在串中的位置。子串在主串中的位置以子串的第一个字符在主串中的位置来表示。
- 两个串的长度相等且每个对应位置的字符都相等时，称这两个串是相等的。
2.串的模式匹配（串的定位操作✪）
子串的定位操作通常称为串的模式匹配，它求的是子串（常称模式串）在主串中的位置。
KMP算法（选择题考点✪）
每次匹配失败之后，无需回溯主串指针，根据next数组的对应关系来决定当前的模式串的指针设置
next数组只与模式串有关，与主串无关利用next数组控制指针回溯的举例
- 此时在第五个元素匹配失败之后，只需要将模式串指针移动到2位置继续与主串的5位置比较
- 移动之后的情况如下
- 此时在第五个元素匹配失败之后，只需要将模式串指针移动到2位置继续与主串的5位置比较
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15int Index_KMP(SString S,SString T,int next[]){
int i=1,j=1;
while(i<=S.length&&j<=T.length){
if(j==0||S.ch[i]==T.ch[j]){
++i;
++j; //继续比较后继字符
}
else
j=next[j]; //模式串向右移动
}
if(j>T.length)
return i-T.length; //匹配成功
else
return 0;
}时间复杂度：O(m+n)
求next数组（选择题考点，手算方法♚）
- next[j]的含义是在子串的第j个字符与主串发生失配时，则跳到子串的next[j]位置重新与主串当前位置进行比较
- 求解方法：
- 首先1号2号位分别固定是0和1
- 若要比较第n位，在上方写出比较字符，只写出其中n-1位前的值（如比较第3位则只需要写出前2位）
下方平行地写出模式串完整字符 - 此时在比较字符的第n位之前画一个竖线，开始进行比较，在下方的模式串进行后移
- 当后移到某一位时，模式串能与上方的比较字符完全匹配时，此时记录当前的模式串位数为next数组中对应位的值
如果模式串已经全部后移出竖线右侧，说明此时next数组的值为1
- 完全匹配的展示
- 例：比较第4位的情况
- 此时画到第四位之前，将模式串逐步后移检查，此时会后移两位才能完全匹配
- 后移到模式串的第一位a时，此时与上方的比较字符的a匹配，此时为第2位，记录在next数组中的序号4位置
- 此时画到第四位之前，将模式串逐步后移检查，此时会后移两位才能完全匹配
对KMP算法的进一步优化（将next数组转变成nextval数组）
nextval数组概述
- 首先需要先把模式串的next数组算出来，初始的nextval数组可以确定第一个序号的值为0
- 此时从前往后（序号2开始）依次观察每个序号对应的next的值所对应的序号的模式串
如下方的序号2的next数组的值为1，1的序号下的模式串为a 若其next数组所对应的序号的模式串的与当前序号的模式串相同，
此时新建立的nextval的值改为其next数组所对应序号的nextval数组的值（2的nextval改为0）
否则与原来的next数组的值一致转换流程（依次转换）
注意：比较字符相同后，赋值是赋予nextval数组的值，而非原数组的值，如下题选C
如果next数组最初的指针是从-1开始，则第一第二序号赋值为-1,0，之后的序号的指针起始位是0，如下题选C；
