字符串

字符串是由字符按顺序排列形成的串结构。
在ACM中会用到两种字符串定义方式：

// C-style string
#define STR_LEN 100
char s1[STR_LEN];

// C++/STL-style string
#include <string>
std::string s2;

C风格字符串本质上就是字符数组；C++/STL风格字符串是将字符数组与其操作抽象集成形成的类，可以说本质上依旧是对字符数组进行操作。

字符串的常用操作

对于C风格字符串而言，所有的字符串操作函数被定义在头文件cstring中，在使用时需要在程序中添加#include<cstring>。

// Index
char a = s1[1];
// Get length -> O(n)
int b = strlen(s1);
// Compare
int c = strcmp(s1, s2);
// Memory set value
memset(s1, 0, sizeof(s1));

对于C++/STL风格的字符串而言，其字符串类定义在头文件string中，在使用时需要在程序中添加#include<string>。

// Index
char a = s1[1];
// Get length -> O(1)
int b = s1.length();
// Compare
bool c = s1 < s2;

大部分程序标准提供的操作函数，编译器提供的都是$$O(n)$$时间复杂度算法。

字符串匹配

字符串匹配就是在一个字符串中寻找另一个字符串的过程，字符串匹配在计算机领域有非常多的应用（搜索引擎、数据库等），其重要程度也不言而喻。
在如下例子中s1是s2的一个匹配，而s3不能匹配其他两个字符串：

s1 = "abc";
s2 = "aaabccc";
s3 = "ac";

匹配算法

由于在C标准函数中没有提供对于任意起始位置寻找匹配的方法（C++STL提供了find方法，但是$$O(n^2)$$复杂度），所以我们一般需要自己实现匹配算法。
在匹配算法中，我们将用于匹配的字符串称为模式串，被匹配的字符串称为匹配串，还是上面那个例子，用s1和s2去匹配，则s1是模式串，s2是匹配串。

暴力匹配

我们很容易能够想到暴力方法实现字符串匹配：

// s1: Match string
// s2: Pattern string
int match(const char s1[], const char s2[]) {
    // Get length
    int l1 = strlen(s1), l2 = strlen(s2);
    // i: Start position of match string
    // lmt: Max posible start position
    for (int i = 0, lmt = l1 - l2; i <= lmt; ++i) {
        // Match flag
        bool f = true;
        // Scanning pattern string
        for (int j = 0; j < l2; ++j)
            if (s1[i + j] != s2[j]) {
                f = false;
                break;
            }
        // Check if matched, then return position
        if (f)
            return i;
    }
    // Not found
    return -1;
}

非常简单明了，就是$$O(n^2)$$的时间复杂度实在是有点不敢恭维了。
接下来我们来看看这样一个例子：

s1 = "abad";
s2 = "abacbcdhijk";

s1作为模式串，s2作为匹配串，来跑一下暴力算法：
一开始是这样的：

我们看到此时s1[i + j]和s2[j]此时一样，所以j会往后走：

接下来两步显然都能匹配，所以我们快进到第三步：

此时发生了失配，所以根据暴力算法，我们移动i，复位j：

但是实际上这样真的好吗？我们发现s2在从b开始时，很明显不可能匹配，因为s1的开头是a，所以更好的移动方法应该是把j移动到1，把i移动到2，因为两个起始位置的a已经可以匹配了：

我们看见此时虽然i和j变了，但是i+j并没有改变，而像这样子的例子其实还有很多，比如下面这个：

如果按照暴力算法来，那么下一步会变成这样：

但是更好的方法其实应该这样：

同样，还是i和j改变了，i+j没有变。
那么这时候我们可以完全不需要i这个变量了，把i+j给定义成一个新的变量k，因为如果按照我们想出的这个跳转方法来看，k一定是递增的，那么接下来就是怎么处理j的跳转和k在什么情况下会递增了。
万幸的是，已经有前人把这种思想变成了一个著名算法——KMP。

KMP算法

KMP算法由D.E.Knuth、J.H.Morris和V.R.Pratt提出的，KMP取的就是他们名字的首字母。
在KMP算法中，核心思想是next[i]数组。
next[i]数组定义为：在字符串s[0..i-1]中最大的公共真前后缀长度。
这里需要说明，一个字符串的真前后缀是不包括这个字符串本身的。
用上面的一个例子：

由于i为0时，字符串s[0..i-1]不存在，所以定义next[0]为-1。
i为1时，字符串a的真前后缀都是空串，所以next[1]为0。
i为2时，字符串ab的真前缀为∅、a，真后缀为∅、b，所以最长的公共前后缀依然是空串，所以next[2]为0。
i为4时，字符串abab的真前缀为∅、a、ab、aba，真后缀为∅、b、ab、bab，所以最长的公共前后缀为ab，所以next[4]为2。
那么这个数组有啥用呢？我们再把上面的例子搬下来，但这次我们把next数组一起弄上去：

下一步：

看！在发生失配之后，j就被赋值成了next[j]。
所以next数组就是帮助j进行跳转的。
那么如何计算next数组呢？其实非常简单：

// const char s[]: Pattern string
// int next: Next array
void getNext(const char s[], int next[]) {
    // s[0..-1] not exists, so assign next[0] to -1
    next[0] = -1;
    // Find next
    for (int i = 0, j = -1; s[i];)
        if(j == -1 || s[i] == s[j]) {
            ++i;
            ++j;
            next[i] = j;
        }
        else 
            j = next[j];
}

需要注意的是，我们如果要使用next数组，一定是使用模式串的next数组。
这个代码实在是非常简单，我们来一步一步演算一下：

一开始的状态如上，要注意的是j此时为-1，其表示next[0]。
由于j为-1，所以下一步i和j都要向后推进，并置next[1]为0，此时才开始正式比较：

此时i和j所指向的字符不同，让j赋值为next[j]：

然后又是推进i和j：

接下来比较i和j指向的字符，他们相等，所以继续推进并修改next数组：

i和j指向字符依然相等，继续：

这里又不相等了，所以回退j为next[j]：

仍然不相等，继续回退：

此时j为-1了，所以到了最后一步：

至此，算法模拟完毕。
经过观察不难看出，i和j其实指示的是一个可能的相同前后缀的结束位置。
我们只要指定了这两个位置，就可以同时推进i和j来检查前后缀是否相等，如果遇到了不相等的情况，那么显然这个最长的长度就是j，表明s[0..j-1]这个前缀和s[i-j+1..i-1]这个后缀是相等的，且长度为j。
那么当i和j失配的时候，为什么要让j等于next[j]来跳转呢？
因为当前的前后缀可能已经不能继续扩展下去了，但是我们利用next[j]可以找到之前已经发现的公共前缀来继续匹配，我们举一个例子：

这里我们试图匹配的前缀和后缀分别是abab和abac，明显无法匹配，所以我们跳转j：

而这里就变成了我们需要试图匹配的前后缀分别为ab和ac，我们之间跳过了一个a和a的匹配，因为我们通过next数组已经知道了他们是一样的，所以我们可以直接快进到ab和ac的匹配。
也就是说，这种操作其实类似于试图把一个前缀“续上”，这样子可以利用已知信息来更新最大长度。
那么知道了next数组，那么按照我们之前发现的匹配方法，就能得到如下代码：

// const char s1[]: Match string
// const char s2[]: Pattern string
// int next[]: Next array
int match(const char s1[], const char s2[], int next[]) {
    for (int i = 0, j = 0; s1[i];)
        if (j == -1 || s1[i] == s2[j]) {
            ++i;
            ++j;
            // If matched, then return position
            if (!s2[j])
                return i - strlen(s2);
        }
        else 
            j = next[j];
    // Not matched
    return -1;
}

模拟演算就不做了，匹配函数和求next函数看起来其实很像，你甚至可以认为求next本质上就是模式串自己在和自己做匹配，即找相同前后缀。
KMP算法比暴力算法已经不知道高到哪里去了，它的时间复杂度为$$O(n+m)$$，其中n和m分别为匹配串和模式串的长度。

优化KMP

朴素的KMP已经能做到很优了，所以再怎么优化也仅仅是停留在常数上了，这就出现了KMP的一种优化写法，这种优化主要体现在next数组的不同上，我们先来看看优化的写法：

// const char s[]: Pattern string
// int next[]: Next array
void getNext(const char s[], int next[]) {
    next[0] = -1;
    for (int i = 0, j = -1; s[i];)
        if (j == -1 || s[i] == s[j]) {
            ++i;
            ++j;
            // ==== Not optimized ====
            // next[i] = j
            // =======================
            next[i] = (s[i] == s[j] ? next[j] : j);
        }
        else 
            j = next[j];
}

我们看到，优化过后主要就是内部修改next数组的部分被换成了一个三目表达式，这个表达式等同于：

if (s[i] == s[j])
    next[i] = next[j];
else 
    next[i] = j;

为啥这么改呢？我们来看看例子：

next_pure是没有优化的next数组，next_optimized是优化过的next数组，乍一看感觉多了很多-1，但是这正是关键所在，我们来用aaaad去匹配aaaac看看。
如果使用未优化的next数组，算法会这样走：
第一到四步：

我们在第五步发生了失配：

这时我们j就要回退了，接下来几步是这样的：

我们发现最后j退回到了-1，因为无论如何匹配，a前缀都无法接到c上，既然如此，那么何不把这些完全没有匹配可能的位置干脆全部置为-1，这样一步就可以到了。
所以这就是KMP的优化（常数）写法，但是需要注意的是，如果采用了这种优化写法，那么KMP算法只能用来完成字符串匹配的工作了，因为我们把next数组的意义给改变了，导致一些本来可以利用next数组性质解决的问题变得不可解。

KMP另类应用

KMP算法不仅仅可以用来字符串匹配，它还有一些另类应用，但是这些其实都是基于next数组的，也就是在以下的应用场景中，你不能使用KMP优化算法。

公共前后缀问题

有些问题需要使用公共前后缀长度，这一类问题基本上按照next数组的定义来解决就可以了，故不多赘述。

循环子串问题

next数组有一个非常特殊的性质：
假设字符串长度为len，则len-next[len]为一个可能的最小循环长度，如果要形成循环，那么需要当且仅当len可以被len-next[len]整除时，即len % (len - next[len] == 0，循环成立，且最大循环数量为len / (len - next[len])，而这个最小的循环节为s[0..len-next[len]-1]。
我们可以简单证明一下这个式子的正确性：
假设有字符串S[0..7]，且已知next[8]为6，所以由next定义可知子串S[0..5]和S[2..7]是一样的。
计算len-next[len]得2，且8可以被2整除，所以最小循环节应该为S[0..1]。
又由子串S[0..5]和S[2..7]相同，故可以得出S[0..1]和S[2..3]相同，S[2..3]和S[4..5]相同，S[4..5]和S[6..7]相同，故证。

参考例题