串

阿杰 like coding bug ❥约 1958 字大约 7 分钟

串的定义

定义：由零个或多个字符组成的有限序列。

记为：S = ' $a_1a_2...a_n$ ' ( $n \geq 1$ )

S是串的名称，其中字符个数称为串的长度。当n = 0时，称其为空串。

串中任意多个连续的子序列称为该串的子串。包含这个子串的字符串称为主串。子串在主串中的位置是子串与主串相同时子串第一个字符在主串中的位置。

如：主串"I AM A PIG"中有个子串"PIG"，子串的位置是8，空格也是需要加入计算的。

通常来说串的基本操作是以子串作为操作对象的，这一点和线性表有着不同。

串的基本操作

strCopy(char *string, char *data)：将data的字符串复制给string
subString(char *string, char *data, int start, int len)：使用string返回data中从start开始长度为len的子串
strLength(char *string)：返回string的长度
index(char *s, char *t)：定位，若s中存在t则返回t的位置，否则返回0
contact(char *s, char *t, char *m)：连接，将t和m连接起来使用s返回
strCompare(char *s, char *t)：比较字符串，s大于t则返回1，s=t返回0，s小于t返回-1
clear(char *s)：将s中的字符全部清除，使其变为空串

根据上面的基本操作可以构建更复杂更强大的功能。

串的存储结构

顺序存储结构

C语言结构体为：

typedef struct String{
    char data[MAX_SIZE];
    int length;    
}

使用这种需要额外添加一个length，用于存储字符串的长度用以避免使用循环获取，其长度是固定的在声明之后无法进行修改长度。

如果添加的字符串长度大于MAX_SIZE就会发生截断。并且串长可以有两种表示方式，一就是上面的那种使用length记录，二是在字符串最后添加一个'\0'，这个是不计入串长的，所以导致获取长度时要遍历。

堆分配存储结构

和之前学习的的链表一样，为了解决“固定”的问题。在上述的顺序结构中一旦初始化，其长度就不能变化了，但是在应用中我们一般不能预见到底需要初始化多长的结构，故采用这种堆分配的结构。

在C语言中，有一个可以自由分配的区域，称其为堆区，使用malloc()和free()进行动态的分配。在之前的代码中也使用了，需要注意的是使用malloc()获取的地址在使用后需要手动调用free()释放。

块链存储结构

也是使用链式存储不过每个节点可以存放多个字符。如上：每个节点存储的字符数为4，如果一个节点中的字符不足就使用 # 填充。

这样呢，让每个节点的存储密度上升了。

串的模式匹配

我们需要知道：

模式串：要进行匹配的字符串
模式匹配：在主串中找到和模式串相同的子串，并返回对应的位置

简单模式匹配

采用的存储结构为第一种，但第一个字符从索引为1开始。简单模式匹配本质就是暴力破解，一次一次遍历主串和模式串，直到匹配到的子串和模式串相等。

显然此种算法的时间复杂度为：O(nm)（n位主串长度，m为模式串长度），在一些情况下有着大量地不必要比较。

C语言表示算法：

int index(String string, String t){
    int i = 1, j = 1;
    while(i <= string.length && j <= t.length){
        if(j.data[i] == t.data[j]){
            i++;
            j++;
        }else{
            i = i - j + 2;
            j = 1;
        }
    }
    if(j > t.length){
        return i - t.length;
    }
    return 0;
}

KMP算法

为了优化上面暴力破解时一些没有必要的比较，于是就诞生了KMP算法。

使用KMP算法时，主串上的i是不会回退的，要么前进，要么不动。

在学习KMP算法之前我们需要知道一些概念：

前缀：除最后一个字符外，字符串的所有头部子串
后缀：除第一个字符外，字符串的所有尾部子串
部分匹配值：字符串的前缀和后缀的最长相等前后缀长度

看着这些概念是模糊的，我们来举个例子：使用字符串 "aabbaa"

子串"a"的前缀和后缀都没有所以最长相等前后缀长度为0

子串"aa"的前缀为{a}后缀为{a}所以最长相等前后缀长度为1

子串"aab"的前缀为{a, aa}后缀为{b, ab}所以最长相等前后缀长度为0

子串"aabb"的前缀为{a, aa, aab}后缀为{b, bb, abb}所以最长相等前后缀长度为0

子串"aabba"的前缀为{a, aa, aab, aabb}后缀为{a, ba, bba, abba}所以最长相等前后缀长度为1

子串"aabbaa"的前缀为{a, aa, aab, aabb, aabba}后缀为{a, aa, baa, bbaa, abbaa}所以最长相等前后缀长度为2

所以字符串的部分匹配值为：0 1 0 0 1 2

我们想一下这个最长相等前后缀长度有什么意义呢？

知道字符串的最长前后缀长度，就知道了这个字符串前面和后面最多有几个字符相等了。如果在匹配过程中遇到不匹配时就可以查询这个部分匹配值表来确定移动的位数，就不用一位一位地移动了，知道这个原理就行了。

维护next数组

在匹配中，如果模式串的第j个字符失配了就跳到next[j]位置上继续比较，这个next数组就是由上面的部分匹配值来的。

在网络上有着多种的next表示的形式，但是究其本质是一样的。具体使用哪一种需要根据题目中的信息来判断，在这里我给出具体的计算方法：

形如[0, 1, 2, 1, 1, 2]；开头为0的next数组。
这个是怎样来的呢？将上面得出来的字符串的部分匹配值右移一位，第一位补0，其余为全部加一。
形如[-1, 0, 1, 0, 0, 1]：开头为-1的next数组。
这个是将第1种的next数组每一位减1得到的。

为什么会有这两种呢？因为是字符串的起始位置定义不同。第1种的起始位置视为1，第2种起始位置视为0。

KMP算法的优化

在使用next数组时其实还是有着缺陷。在某些时候还是会有多余地比较，所有在这里继续对其优化，得到nextval数组。

优化方法：首先得到next数组，nextval数组的第一位是和next数组中的第一位一样的，然后比较next[i]对着的模式串字符和模式串[next[i]]，若两者相等则nextval[i]就为模式串[next[i]]对应的nextval值，否则nextval[i]就为next[i]。

下面举个例子：

字符串："aabbaa"

采用开头为0的next数组
部分匹配值为：[0, 1, 0, 0, 1, 2]
next数组：[0, 1, 2, 1, 1, 2] （右移并加1 补0）
nextval数组：[0, 0, 2, 1, 0, 0] （进行比较）
采用开头为-1的next数组
next数组为：[-1, 0, 1, 0, 0, 1] （每位减1）
nextval数组为：[-1, -1, 1, 0, -1, -1] （进行比较）

这一部分最重要的就是KMP算法，出题为算next数组、nextval数组、比较次数、滑动距离。