拓展kmp

作用：求母串s的子串s[i; |s|]与模式串t的最长公共前缀，其中i = 0, 1, …, |s|。
代码如下：

void get_next(char t[maxn]){
    int d = (int)strlen(t);
    nex[0] = d;
    int i = 0;
    while(i + 1 < d && t[i] == t[i + 1]) ++i;
    nex[1] = i;
    int p = 1;
    for(int i = 2; i < d; i++){
        if(nex[i - p] + i < nex[p] + p) nex[i] = nex[i - p];
        else{
            int j = p + nex[p] - i;
            if(j < 0) j = 0;
            while(i + j < d && t[i + j] == t[j]) j++;
            nex[i] = j; p = i;
        }
    }
}

void exkmp(char s[maxn], char t[maxn]){
    int i = 0;
    int d1 = (int)strlen(s), d2 = (int)strlen(t);
    while(i < d1 && i < d2 && s[i] == t[i]) i++;
    ext[0] = i;
    int p = 0;
    for(int i = 1; i < d1; i++){
        if(nex[i - p] + i < p + ext[p]) ext[i] = nex[i - p];
        else{
            int j = p + ext[p] - i;
            if(j < 0) j = 0;
            while(i + j < d1 && j < d2 && s[i + j] == t[j]) j++;
            ext[i] = j;
            p = i;
        }
    }
}

有几点值得注意：
1.next数组的获取需要对0和1都进行初始化才行。
2.在循环过程中的if语句判断，必须是严格的小于号才行，如果连续的长度正好能够延伸到p - 1 + nex[p]，那么我们无法判断之后是否还会出现相同的字符，仍需要往后判断；只有严格的小于最远点，才能确保已经出现了一个不同点从而无需再往后判断。

---

Trie字典树

trie树支持insert、find、erase操作。
具体代码实现略。

---

AC自动机

推荐博客两篇：
强势图解AC自动机
AC自动机–yyb

三道例题：
P3808 【模板】AC自动机（简单版）
P3796 【模板】AC自动机（加强版）
P5357 【模板】AC自动机（二次加强版）

我们先考虑前两个比较友善的问题
第一个问题要求的是出现的模式串的种数，第二个要求的是出现次数最多的模式串。相比于第一个问题，只需要在第二个中增添一个数组记录这个end是哪一个模式串的末尾即可，最后在查询的时候搜到一个end就把times += e[p]即可。

两道题的区别在于，第一个只需要求种数，所以我们在res +=e [p]之后需要置e[p] = -1。一方面可以稍微的优化一下时间复杂度，另一方面可以保证算法的正确性（不然，我们求的就是所有模式串出现的次数，而不是出现的种数！）。而第二个题目要求的是出现次数，所以我们不能修改e[p]，而应该不断的累加从而产生答案。

对于第二个问题，值得一提的是，重复的元素并不会影响我们的答案。因为重复字符串的贡献已经算在了e[p]其中，而在我们统计个数的时候一定有某一个字符串拥有着这个e[p]（自然地，其余的相同串的times == 0）

通过这两道题的研究，我大概把最基本的AC自动机结构搞明白了，可以不看板子正确快速地撸出一个AC自动机了。但是加强版跑下来用了9s…内存用了一百多M…

有一位聚聚的时间、空间消耗都好优秀啊～我查询了一下各类题解，发现有一个名叫fail 树的结构可以高效的对AC自动机进行优化，所以我打算稍后再研究一下这个Fail树。

二次加强版