串

串

串：是由零个或多个字符组成的有限序列。一般记作

存储结构

• 顺序存储
• 堆分配存储
• 块链存储

顺序存储

固定最大长度 计算串长的两种方式：

1. 在结构中使用额外的变量 len；
2. 在串尾部加一个不计长度的结束标记符 \0；

堆分配存储

也是一组地址连续的存储单元存放串值得字符序列，但区别于顺序存储需要在程序执行前确定空间大小即固定长度。堆分配可以在程序执行中动态分配；

块链储存

用链表的方式存储串值，可以一个结点存储一个字符，也可以一个结点存储多个字符（所以称之为块链结构），若串长不是结点数的整数倍（换言之结尾结点可能无法被填满），通常在结点没放满的时候填充 #。

串模式匹配算法

模式匹配：字串的定位操作。

1. 简单的串模式匹配算法——暴力匹配
2. 改进的串模式匹配算法——KMP 算法

简单的串模式匹配算法

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(mn)$。

改进的串模式匹配算法——KMP 算法

分析以上算法，容易发现算法出现了多余的步骤。假设从 j 匹配到 i 位置发现匹配不上了，那么很有可能从 j 到 i 都是匹配不上的，然而算法还是 j+1 进行下一次匹配，因此会增加很多次不必要的循环次数。所以改进目标就是通过预先分析，得知下一次应该从哪里再次匹配才可能匹配上，以减少不必要的循环次数；

KMP 算法事先对串进行分析得到一张判断该跳过几个字符进行匹配的表格，根据这张表格，我们可以适当跳过一些必然不会匹配成功的字符，从而减少了循环次数。

前缀：指除最后一个字符以外，字符串所有头部子串，例如 'abcd' 的前缀有 'a','ab','abc' 后缀：指除第一个字符以外，字符串所有尾部子串，例如 'abcd' 的后缀有 'd','cd','bcd' 部分匹配值(Partial Match)：指一个字符串的前缀和后缀的公共子串中最长的长度，例如 'abcabc' 的部分匹配值为 3；

next 表：

上表是字符串 S 的 next 表，编号 j 的 next 字段的值表示从 1 号到 j-1 号位的字符串的部分匹配值 +1，第一位默认为 0； next 表给出了已匹配成功的子串的部分匹配值， next[j] 的含义是子串在j-2-next[j] ~ j-1 部分的串和从 0 ~ next[j]-1 长的串是一样的。 KMP 算法步骤：

1. 分析子串得到 PM 表；
2. 开始遍历字符串去匹配子串；
3. 当主串遍历到 i 子串遍历到 j 时出现不匹配的情形，根据 next 表得到 next[j]；
4. 子串指针从 next[j] 开始继续与主串当前位置进行匹配；

这样主串的指针便不需要回退，主串指针只需要从头遍历到尾便能够完成匹配。总算法复杂度从暴力匹配的 $O(mn)$ 优化到了 $O(n+m)$。

为什么只要子串指针的跳变就能够完成匹配？

假设主串在 i 位置，子串在 j 位置匹配不上了，子串从 0 ~ next[j]-1 部分的串和主串 i-next[j] ~ i-1 是能够匹配上的，所以直接将子串的开头对齐到主串中最近匹配上的 next[j] 个字符的位置即可。 主串：'... abcabcd ...' 子串：'abcdabca ...' 例如上面的两个串进行匹配，当匹配到第 8 位的时候就匹配不上了，这时将子串往前移动对齐到主串的第二个 abc 处（即子串指针从第 4 位开始匹配）。

KMP 算法优化

我们继续思考，串匹配时，主串的 S[i] 和子串的 P[j] 开始不匹配了，我们将子串从 P[next[j]] 开始继续与主串从 S[i] 匹配。但若出现了 P[j]=P[next[j]] 那么我们是不是又进行了无意义的比较？ 于是我们对 next 数组进行优化，将 P[j]=P[next[j]] 的部分的 next[j] 换成 next[next[j]] 如果 P[next[j]] = P[next[next[j]]] 那么就继续递归修改值，直至变成 0；

例如：