KMP

一个人能走多远不在于他在顺境时能走的多快，而在于他在逆境时多久能找到曾经的自己

强烈建议看 胡凡 算法笔记 P455

KMP字符串 —— 深入浅出 next 数组

假设下标从1开始。字符串 S[1,N]，子串 P[1,M]，S 指针 i-1，P 指针 j

next[j]

• 子串中，以 j 为终点的后缀 与 从1开始的前缀相等的最长长度 x
• \(P[1,x] = P[j-x+1,j]\)

kmp 建议看算法笔记

1. i-1 与 j 对应字符相同；i 与 j+1 对应字符不同。此时需要把红颜色子串往后移动，为了移动最少需要 next[j]
2. 让 j = next[j]，从线2变为线3（线1红色部分 等于 线3红色部分）
3. 继续匹配 i 与 j+1，若发现不匹配，再 j = next[j] （递归进行）
4. 当 j = m，意味着找到子串，然后 j = next[j] 继续寻找

时间复杂度计算

• 生成next数组 \(O(m)\)
• 字符串每个字符被遍历一次，\(O(n)\)
• j++ 最多 n 次，最多减 n 次，\(O(n)\)

831 ???

831. KMP字符串 - AcWing题库

next 在某些头文件里有定义，最好换个变量名；另外KMP算法还可以进一步优化，以下是优化后的算法

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1e5 + 10;
const int M = 1e6 + 10;
int next_val[N];

int main() {
    int n, m;
    char p[N], s[M];
    cin >> n >> p + 1 >> m >> s + 1;
    // ^ 生成 next_val 数组
    for (int i = 2, j = 0; i <= n; i++) {
        while (j && p[i] != p[j + 1]) j = next_val[j];
        if (p[i] == p[j + 1]) j++;
        // ^ 继续优化，选择回退的最佳位置
        if (j && p[i + 1] == p[j + 1]) {
            next_val[i] = next_val[j];
        } else
            next_val[i] = j;
    }
    // for (int i = 1; i <= n; i++) {
    //     cout << next_val[i] << endl;
    // }
    // ^ KMP 匹配过程
    for (int i = 1, j = 0; i <= m; i++) {
        while (j && p[j + 1] != s[i]) j = next_val[j];
        if (p[j + 1] == s[i]) j++;
        if (j == n) {
            cout << i - n << " ";
            j = next_val[j];
        }
    }
    return 0;
}

字典树 Trie

用于高效存储和查找字符串集合的数据结构

835

835. Trie字符串统计 - AcWing题库

son[N][26] 存的是每个节点所有的儿子是什么，cnt[N] 存的是单词的数量，idx与数组模拟单链表里的idx相同

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int son[N][26], cnt[N], idx;  // ^ 下标是0的点，既是根节点又是空节点

void insert(char str[]) {
    int p = 0;
    for (int i = 0; str[i]; i++) {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p]++;
}

int query(char str[]) {
    int p = 0;
    for (int i = 0; str[i]; i++) {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

int main() {
    cin.tie(0);
    int n;
    cin >> n;
    while (n--) {
        char a, b[N];
        cin >> a >> b;
        if (a == 'I')
            insert(b);
        else
            cout << query(b) << endl;
    }
    return 0;
}

143 ??

143. 最大异或对 - AcWing题库

朴素算法是两层循环并满足 j<i（避免重复， \(C^2_n = n*(n-1)/2\) ）；时间复杂度 \(O(n^2)\) ，题目给的 n 是 1e5，则 1e10 超时

可以使用 trie tree 优化，每插入一个元素 x，在字典树中查找满足与该元素异或最大值的元素（尽可能反着取，每次查找只要遍历31位），时间复杂度 \(O(n)\)

可以先插入再遍历（少个判断），第一个插入的元素与自身异或为 0

每个节点个数长31，最多1e5个，那么idx最大可以到 31 * 1e5