串 | 爱丽丝邦邦！

串的逻辑结构和线性表极为相似。区别仅仅是串把数据对象现代为字符。但是串的操作和线性表差别很大。线性表的操作都是以单个数据元素为单位进行操作的，但是串通常是以连续的子串作为操作基本单位。

实现

数据结构定义

这个是“定长顺序存储表示“（静态分配内存，静态的顺序存储）。

cpp

#define MAXLEN 255
typedef struct{
    char ch[MAXLEN];
    int length;
}SString;

i和j从1开始，使用位序的想法，[0]位不用的。

你也可以使用“堆分配存储表示”（动态分配内存，动态的顺序存储），也可以用“块链存储表示”（链表，动态的链式存储）。这些和之前线性表都是一模一样的。

模式匹配

模式匹配简单说就是搜索子串。被搜索的那个串叫模式串。我们的目标是在主串里找到模式串出现的位置。

简单模式匹配算法

或者叫朴素模式匹配/BF算法。暴力算法。

cpp

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;
}

i指向主串，j指向模式串。如果发现某个字符和模式串匹配上了，那么两者指针就加，继续检查下面的字符匹不匹配。如果不匹配了，那就把i和j的状态重置回第一次发现的时候，i再加1，重新开始尝试匹配。比如说，i到6了，j到3了，发现此时不一样。当时在i=4,j=1的时候开始了匹配，要恢复到这个i的状态，则需要让i减去(j-1)。但是回到这个位置会循环进入同一个错误的匹配。所以还需要再加1.-(j-1)+1就是-j+2，所以是i=i-j+2;

如果i到头了，没法匹配了，那就退出，如果j到头，就是匹配到了，也退出。在循环外面用j>T.length来判断是哪种情况。

暴力匹配会出现一个明确的性能问题：i（对主串的指针）会发生回溯，也就是会往回走。往回走会导致时间复杂度不是线性的，O(mn)。如果有一种方法能够让i不发生回溯，那么就能让时间复杂度变成线性的,O(m+n)。
你会发现，回溯的那部分，是主串的i-j到i-1的这部分，这部分和模式串的前面部分是一致的。每一次后移都会对模式串的前面部分进行重新匹配。这一部分能不能省呢？可以，这就是kmp算法。

KMP算法

前缀：一个串集合，包含字符串从第一个字符开始，到字符串除了最后一个字符以外其他所有位置的子串的集合。‘abab’的前缀为{'a','ab','aba'}
后缀：一个串集合，包含字符串从除了第一个字符以外其他所有位置开始，到字符串的最后一个字符的子串的集合。‘abab’的后缀为{'bab','ab','b'}
部分匹配值：前后缀最长相等的串长度。就是两个集合的交集里子串的最长长度。‘abab’的前后缀交集为{'ab'}，其中最长的长度是2,所以’abab’的部分匹配值是2.
部分匹配值表：从一个字符开始一个一个字符变长直到完整字符串的所有子串组成的数表。比如模式串’ababa’的部分匹配值表是00123，分别为’a’、‘ab’、‘aba’、‘abab’、‘ababa’的部分匹配值。2就是上面’abab’的结果。

匹配：
主串：ababcabcacbab
模式串：abcac

这个模式串的部分匹配值表是00010

开始匹配

第1次匹配：主串1-2的ab和模式串1-2的ab匹配了。但是第三个不匹配。查表发现’ab’对应的部分匹配值是0.依照公式计算接下来模式串的右滑位数（将模式串和主串对在一起时模式串的偏移值）右滑位数=已经成功匹配的字符串的长度-已经成功匹配的字符串对应部分匹配值。所以滑动2位。现在模式串对齐了主串的第3位。

第2次匹配：主串3-6的abca和模式串1-4的abca匹配了。但是第4个不匹配。对应部分匹配值是1,右滑位数算出是3,右滑3位，现在模式串对齐了主串的第6位。

第3次匹配：主串6-10的abcac和模式串直接匹配，查找结束。

有一种特例，如果第一个位置就没匹配上，成功匹配的字符串为空串，怎么办？此时让模式串右移1位。

那么现在解释，为什么这样就可以搞？
我们把这个例子的第2到第3次匹配拿出来看。
第2次的时候，abca匹配上了，但是第5个字符失配。如果是暴力算法，那么每次只挪一位，下一次会去比主串的b和模式串的a，再下一次会去比主串的c和模式串的a，再再下一次才会去比主串的a和模式串的a，才匹配上。但是kmp可以一步到位，直接到主串的下一个a。为什么可以这样？因为我们发现了刚才已匹配的串的规律。已匹配的串是‘abca’。我们发现它的前缀中有个’a’，后缀也有个’a’，它的一个前缀串和后缀串是相同的！这就是刚才部分匹配值的求解。所以下一次可以直接从后缀的那个位置开始比较。为什么不可能从中间开始下一次比较？因为它们一定匹配不上模式串的匹配，一定可以预知它们的匹配注定失败。那么这个移动需要移动几位呢？我们希望主串的这一部分的后缀能够和模式串的前缀对齐：
所以，滑动的位数 = 已匹配的长度(4) - 最长相等前后缀长度(1) = 3。

kmp是根据已经匹配上的串的结构，排除了一定无法被匹配的那些可能性，让一次滑动的长度尽可能大，跳到最有可能的位置。

所以他相比暴力多利用了什么？利用的是已经匹配上的那部分。暴力算法把这一部分信息浪费掉了，导致前面这些匹配被一次次循环做。

代码实现

前面的过程已经完整的实现了kmp算法。实际代码里面没有什么滑动这种草稿纸上画画的直观说法，有的只有指针。在实际实现中，我们定义next数组。next[j]表示失配了以后，j应该跳到模式串的什么位置。

手算next数组的方法

next[1]。表示尝试匹配第一个就失败了。就是上面那个特例。此时令next[1]为0,然后ij都+1.
next[2]。next[2]为1.下一次j从1开始，i不动。相对于右滑1位。
next[3]。next[3]为1.下一次j从1开始，i不动。相对于右滑2位。
next[4]。next[4]为1.下一次j从1开始，i不动。相对于右滑3位。
next[5]。next[5]为2.下一次j从2开始，i不动。相对于右滑3位。
next[j] = j - 右滑位数 = j - (已匹配字符数 - 已匹配字符串的部分匹配值) = j - ((j-1)-PM[j-1]) = PM[j-1] + 1.

计算机算next的方法

TODO
本部分未完成

首先给出next[j]的数学描述：

$$ \text{next}[j]= \begin{cases} 0, & j=1 \\ \max\{k\mid 1<k<j \text{且} \text{'}P_1\cdots P_{k-1}\text{'}=\text{'}P_{j-k+1}\cdots P_{j-1}\text{'}\}, & \text{当此集合不为空时} \\ 1, & \text{其他情况} \end{cases} $$

第二个实现起来还是很难，那样的话要计算机去把PM表算出来。计算机不适合去去算出部分匹配值表PM，因为时间复杂度很高，人可以一眼看出，所以前面的方法只能给人理解和手推。计算机要用递归达到O(n)的复杂度。

下面是递推：
设next[j]=k,那么next[j+1]是多少呢？

代码

TODO
本部分未完成