Chapter4 串

\[ 串 \begin{cases} 基本概念：主串、子串、串长\\ 存储结构\begin{cases}定长顺序存储\\堆分配存储\\块链存储\end{cases}\\ 模式匹配算法\begin{cases}暴力匹配法\\KMP算法——next数组\\KMP算法改进——nextval数组\end{cases}\\ \end{cases}\\ \]

4.1 串的定义和实现

字符串简称串，计算机上非数值处理的对象基本都是字符串数据。

4.1.1 串的定义

串是由零个或多个字符组成的有限序列，字符的个数n称为串的长度。当n=0时称为空串

串中任意多个连续的字符组成的子序列称为该串的子串。子串在串中的位置以第一个字符的位置来表示。

串和线性表的逻辑结构相似，区别在于串的数据对象限定为字符集。操作上，线性表以元素作为操作对象，串以子串为操作对象。

4.1.2 串的存储结构

定长顺存储表示

类似于线性表的顺序存储结构，用一组地址连续的存储单元来存储串的字符序列。为每个串变量分配一个固定长度的存储区，即定长数组
```
#define MAXLEN 255      //预定义最多串长为255
typedef struct{
    char ch[MAXLEN];    //每个分量存储一个字符
    int length;         //串的实际长度
}SString;
```
串的长度超过MAXLEN时会被舍去，称为截断。串长有两种表示方法：一种是如上定义一个额外变量length来存放串长度；另外一种是在串值后加入截止符，例如'\0'，串长为隐含值遍历获取。
堆分配存储表示

堆分配存储仍然以一组地址连续的存储单元存放串值的字符序列，但它们的存储空间是在程序执行过程中动态分配的
```
typedef struct{
    char *ch;       //按串长分配存储区，ch指向串的基地址
    int length;     //串的长度
}HString;
```
在C中，存在一个自由存储区“堆”，并且用malloc()和free()函数来完成动态存储管理。利用malloc()为每个新产生的串分配一块实际串长所需的存储空间。已分配的空间可用free()释放。
块分配存储表示

类似于线性表的链式存储，可以采用链表方式存储串值。但串相较于链表，每个结点既可以存放一个字符，也可以存放多个字符。故每个结点称为块。

4.2 串的模式匹配

子串的定位操作通常称为串的模式匹配。它求的是子串（也称模式串）在主串中的位置。

4.2.1 简单的模式匹配算法

简单的模式匹配，即不依赖于其他串操作的暴力匹配算法。这里采用定长顺序存储结构。

算法思想：从主串S的第一个字符开始，与模式串T的第一个字符比较，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起，重新和模式串的字符比较；以此类推

int Index(SString S,SString T){
    int i=1,j=1;
    while(i<=S.length && j<=T.length){
        if(S.ch[i]==T.ch[j]){
            ++i,++j;            //继续比较后续字符
        }
        else{
            i=i-j+2;            //主串起始字符后退一位，重新开始匹配
            j=1;
        }
    }
    if(j>T.length) return i-T.length;
    else return 0;
}

简单模式匹配算法的最坏时间复杂度为O(nm)，其中n和m分别为主串和模式串的长度。

4.2.2 串的模式匹配算法——KMP算法（主串指针不回溯）

简单模式匹配（暴力匹配）中，每趟匹配失败都是模式串后移一位在从头开始比较。而某趟已匹配相等的字符序列是模式串的某个前缀，这种频繁的重复比较相当于模式串不断进行自我比较，即低效率的根源。

因此，若已匹配相等的前缀序列中有某个后缀正好是模式串的前缀，则可将模式串向后滑动到与这些相等字符对齐的位置。主串指针i无需回溯，并从该位置继续开始比较。

模式串向后滑动的位数的计算仅与模式串本身的结构有关，而与主串无关。

next数组

4.2.3 KMP算法的进一步优化

nextval数组