1
问题：在文本串 S 中找模式串 P 的所有出现位置。
2

3
暴力匹配：O(n*m)
4
  每次匹配失败后，S 的指针只前进 1 步 → 大量重复比较
5

6
KMP (1977)：O(n+m)
7
  预处理 P 的"前缀函数" → 匹配失败时，利用已知信息跳过
8

9
Rabin-Karp (1987)：O(n+m) 平均
10
  用哈希快速比较 → 只有哈希相同时才逐字符验证
11

12
AC 自动机 (1975)：O(n + total_matches)
13
  把多个模式串建成 Trie + fail 指针 → 一次扫描匹配所有模式
14

15
Manacher (1975)：O(n)
16
  专门解决最长回文子串的 O(n) 算法

1
// 多项式哈希：hash(s) = (s[0]*base^{n-1} + s[1]*base^{n-2} + ... + s[n-1]) % MOD
2
class StringHash {
3
    using ULL = unsigned long long;
4
    static const ULL BASE = 131;     // 常用基数：131, 13331
5
    static const ULL MOD  = 1e9 + 7; // 或直接用 ULL 自然溢出
6

7
    std::vector<ULL> _hash;   // _hash[i] = s[0..i-1] 的哈希
8
    std::vector<ULL> _power;  // _power[i] = BASE^i
9

10
public:
11
    explicit StringHash(const std::string& s) {
12
        int n = s.size();
13
        _hash.resize(n + 1);
14
        _power.resize(n + 1);
15

16
        _hash[0] = 0;
17
        _power[0] = 1;
18
        for (int i = 0; i < n; ++i) {
19
            _hash[i + 1] = (_hash[i] * BASE + s[i]) % MOD;
20
            _power[i + 1] = (_power[i] * BASE) % MOD;
21
        }
22
    }
23

24
    // 子串 s[l..r] 的哈希值（0-indexed，闭区间）
25
    ULL getHash(int l, int r) const {
26
        return (_hash[r + 1] - _hash[l] * _power[r - l + 1] % MOD + MOD) % MOD;
27
    }
28
};
29

30
// 使用示例：
31
// StringHash sh("hello");
32
// sh.getHash(1, 3) → "ell" 的哈希

1
#include <vector>
2
#include <string>
3

4
// 构建 next 数组（也称为 pi 数组 / 前缀函数）
5
std::vector<int> buildNext(const std::string& pattern) {
6
    int m = pattern.size();
7
    std::vector<int> next(m, 0);
8

9
    // j = 当前已匹配的前缀长度
10
    for (int i = 1; i < m; ++i) {
11
        int j = next[i - 1];  // 上一位置的前缀函数值
12

13
        // 回退：当前字符不匹配时，沿 next 链回退
14
        while (j > 0 && pattern[i] != pattern[j]) {
15
            j = next[j - 1];
16
        }
17

18
        if (pattern[i] == pattern[j]) {
19
            ++j;
20
        }
21
        next[i] = j;
22
    }
23
    return next;
24
}
25

26
// KMP 字符串匹配
27
std::vector<int> kmpSearch(const std::string& text, const std::string& pattern) {
28
    int n = text.size(), m = pattern.size();
29
    if (m == 0) return {};
30

31
    auto next = buildNext(pattern);
32
    std::vector<int> matches;
33

34
    int j = 0;  // 当前已匹配的模式串长度
35
    for (int i = 0; i < n; ++i) {
36
        // 不匹配时，沿 next 数组回退（j 可能回退多次）
37
        while (j > 0 && text[i] != pattern[j]) {
38
            j = next[j - 1];
39
        }
40

41
        if (text[i] == pattern[j]) {
42
            ++j;
43
        }
44

45
        if (j == m) {  // 完全匹配
46
            matches.push_back(i - m + 1);
47
            j = next[j - 1];  // 继续找下一个匹配
48
        }
49
    }
50
    return matches;
51
}

1
// 面试最简版本：把 next 构建和匹配合并为同一个模板
2
// next[i] = 以 i 结尾的最长相等前后缀长度
3
int strStr(std::string haystack, std::string needle) {
4
    if (needle.empty()) return 0;
5
    int n = haystack.size(), m = needle.size();
6

7
    // 1. 构建 next
8
    std::vector<int> next(m, 0);
9
    for (int i = 1, j = 0; i < m; ++i) {
10
        while (j > 0 && needle[i] != needle[j]) j = next[j - 1];
11
        if (needle[i] == needle[j]) ++j;
12
        next[i] = j;
13
    }
14

15
    // 2. 匹配
16
    for (int i = 0, j = 0; i < n; ++i) {
17
        while (j > 0 && haystack[i] != needle[j]) j = next[j - 1];
18
        if (haystack[i] == needle[j]) ++j;
19
        if (j == m) return i - m + 1;
20
    }
21
    return -1;
22
}

1
#include <vector>
2
#include <string>
3
#include <queue>
4

5
struct AhoCorasick {
6
    static constexpr int ALPHABET = 26;
7

8
    struct Node {
9
        int next[ALPHABET] = {};  // 子节点
10
        int fail = 0;              // fail 指针
11
        int output = 0;            // 以此节点结尾的模式串数量（或模式串ID列表）
12
    };
13

14
    std::vector<Node> trie;
15

16
    AhoCorasick() : trie(1) {}  // root 在索引 0
17

18
    // 插入一个模式串
19
    void insert(const std::string& pattern) {
20
        int node = 0;
21
        for (char c : pattern) {
22
            int idx = c - 'a';
23
            if (trie[node].next[idx] == 0) {
24
                trie[node].next[idx] = trie.size();
25
                trie.emplace_back();
26
            }
27
            node = trie[node].next[idx];
28
        }
29
        ++trie[node].output;  // 标记为模式串结尾
30
    }
31

32
    // 构建 fail 指针（BFS）
33
    void build() {
34
        std::queue<int> q;
35

36
        // 第一层：root 的直接子节点的 fail 指向 root
37
        for (int c = 0; c < ALPHABET; ++c) {
38
            int child = trie[0].next[c];
39
            if (child) {
40
                trie[child].fail = 0;
41
                q.push(child);
42
            }
43
        }
44

45
        while (!q.empty()) {
46
            int node = q.front(); q.pop();
47

48
            for (int c = 0; c < ALPHABET; ++c) {
49
                int child = trie[node].next[c];
50
                if (!child) continue;
51

52
                // 找 child 的 fail：
53
                // 沿父节点的 fail 链找第一个也有子节点 c 的节点
54
                int f = trie[node].fail;
55
                while (f != 0 && trie[f].next[c] == 0) {
56
                    f = trie[f].fail;
57
                }
58
                trie[child].fail = trie[f].next[c];
59

60
                // 合并 output：child 也匹配了其 fail 路径上所有的模式串
61
                trie[child].output += trie[trie[child].fail].output;
62

63
                q.push(child);
64
            }
65
        }
66
    }
67

68
    // 在文本中搜索所有模式串
69
    int search(const std::string& text) {
70
        int node = 0;
71
        int totalMatches = 0;
72

73
        for (char ch : text) {
74
            int c = ch - 'a';
75

76
            // 失配时沿 fail 链跳转
77
            while (node != 0 && trie[node].next[c] == 0) {
78
                node = trie[node].fail;
79
            }
80

81
            node = trie[node].next[c];
82
            totalMatches += trie[node].output;
83
        }
84
        return totalMatches;
85
    }
86
};

1
// 找所有出现超过一次的 10 字符子串
2
// Rabin-Karp 的典型应用：滚动哈希 + 频次统计
3
std::vector<std::string> findRepeatedDnaSequences(std::string s) {
4
    if (s.size() < 10) return {};
5

6
    std::unordered_map<int, int> count;  // hash → 出现次数
7
    std::vector<std::string> result;
8

9
    // 用 2-bit 编码 A/C/G/T → 20 bit 就可以存一个 10-gram
10
    const int L = 10;
11
    std::unordered_map<char, int> code = {{'A', 0}, {'C', 1}, {'G', 2}, {'T', 3}};
12
    const int mask = (1 << (2 * L)) - 1;  // 低 20 位为 1
13

14
    int hash = 0;
15
    for (int i = 0; i < s.size(); ++i) {
16
        hash = ((hash << 2) | code[s[i]]) & mask;  // 滚动哈希
17
        if (i >= L - 1) {
18
            if (++count[hash] == 2) {
19
                result.push_back(s.substr(i - L + 1, L));
20
            }
21
        }
22
    }
23
    return result;
24
}

1
// 在字符串前面添加字符使其成为回文串，求最短
2
// KMP 思路：找 s 的"最长回文前缀" = s 和 reverse(s) 的最长公共前缀
3
std::string shortestPalindrome(std::string s) {
4
    if (s.empty()) return "";
5

6
    std::string rev(s.rbegin(), s.rend());
7
    std::string combined = s + "#" + rev;  // '#' 分隔防止越界匹配
8

9
    // 对 combined 构建 next 数组
10
    int m = combined.size();
11
    std::vector<int> next(m, 0);
12
    for (int i = 1; i < m; ++i) {
13
        int j = next[i - 1];
14
        while (j > 0 && combined[i] != combined[j]) {
15
            j = next[j - 1];
16
        }
17
        if (combined[i] == combined[j]) ++j;
18
        next[i] = j;
19
    }
20

21
    // next.back() = s 的最长回文前缀长度
22
    int prefixLen = next.back();
23
    return rev.substr(0, s.size() - prefixLen) + s;
24
}

1
// 大数乘法：模拟竖式乘法
2
std::string multiply(std::string num1, std::string num2) {
3
    if (num1 == "0" || num2 == "0") return "0";
4

5
    int m = num1.size(), n = num2.size();
6
    std::vector<int> result(m + n, 0);
7

8
    // 从低位到高位
9
    for (int i = m - 1; i >= 0; --i) {
10
        for (int j = n - 1; j >= 0; --j) {
11
            int mul = (num1[i] - '0') * (num2[j] - '0');
12
            int sum = mul + result[i + j + 1];  // 加上之前的进位
13

14
            result[i + j + 1] = sum % 10;        // 当前位
15
            result[i + j]     += sum / 10;       // 进位
16
        }
17
    }
18

19
    // 转为字符串
20
    std::string ans;
21
    for (int digit : result) {
22
        if (!(ans.empty() && digit == 0)) {  // 跳过前导零
23
            ans += ('0' + digit);
24
        }
25
    }
26
    return ans;
27
}

1
// 单敏感词检查：KMP
2
bool containsBadWord_KMP(const std::string& message,
3
                          const std::string& badWord) {
4
    return !kmpSearch(message, badWord).empty();
5
}
6

7
// 多敏感词检查：AC 自动机（一次扫描匹配所有敏感词）
8
class SensitiveWordFilter {
9
    AhoCorasick _ac;
10

11
public:
12
    void loadWords(const std::vector<std::string>& badWords) {
13
        for (const auto& word : badWords) {
14
            _ac.insert(word);
15
        }
16
        _ac.build();
17
    }
18

19
    int countMatches(const std::string& message) {
20
        return _ac.search(message);
21
    }
22

23
    bool isClean(const std::string& message) {
24
        return countMatches(message) == 0;
25
    }
26
};

1
// 对大文件做内容去重：用滚动哈希快速计算文件指纹
2
// 不需要把整个文件读入内存
3
#include <fstream>
4

5
uint64_t fileFingerprint(const std::string& filePath, int sampleSize = 4096) {
6
    std::ifstream file(filePath, std::ios::binary);
7
    if (!file) return 0;
8

9
    const uint64_t BASE = 131;
10
    uint64_t hash = 0;
11
    char buffer[4096];
12

13
    // 读文件头部
14
    file.read(buffer, sampleSize);
15
    for (int i = 0; i < file.gcount(); ++i) {
16
        hash = hash * BASE + (unsigned char)buffer[i];
17
    }
18

19
    // 跳到文件尾部
20
    file.seekg(-std::min(sampleSize, (int)file.tellg()), std::ios::end);
21

22
    // 读文件尾部并混合
23
    file.read(buffer, sampleSize);
24
    for (int i = 0; i < file.gcount(); ++i) {
25
        hash = hash * BASE + (unsigned char)buffer[i];
26
    }
27

28
    // 混合文件大小
29
    file.seekg(0, std::ios::end);
30
    hash = hash * BASE + file.tellg();
31

32
    return hash;
33
}

1
// 文件系统路径的前缀匹配："/assets/textures/ui/" 下所有资源
2
// 用前缀哈希 + Trie 实现快速查找
3
class ResourcePathIndex {
4
    struct PathNode {
5
        std::unordered_map<std::string, int> children;  // 目录名 → 子节点
6
        std::vector<int> assets;                        // 此路径下的资源 ID
7
    };
8

9
    std::vector<PathNode> _nodes;
10

11
public:
12
    ResourcePathIndex() : _nodes(1) {}
13

14
    void insert(const std::string& path, int assetId) {
15
        int node = 0;
16
        size_t start = 0;
17

18
        while (start < path.size()) {
19
            size_t slash = path.find('/', start);
20
            std::string dir = path.substr(start, slash - start);
21
            start = slash + 1;
22

23
            if (_nodes[node].children.count(dir) == 0) {
24
                _nodes[node].children[dir] = _nodes.size();
25
                _nodes.emplace_back();
26
            }
27
            node = _nodes[node].children[dir];
28
        }
29
        _nodes[node].assets.push_back(assetId);
30
    }
31

32
    // 查询某目录下的所有资源
33
    std::vector<int> query(const std::string& directory) {
34
        int node = 0;
35
        size_t start = 0;
36

37
        while (start < directory.size()) {
38
            size_t slash = directory.find('/', start);
39
            std::string dir = directory.substr(start, slash - start);
40
            start = slash + 1;
41

42
            if (_nodes[node].children.count(dir) == 0) {
43
                return {};  // 路径不存在
44
            }
45
            node = _nodes[node].children[dir];
46
        }
47
        return _nodes[node].assets;
48
    }
49
};

1
// 检测玩家是否用回文模式刷屏
2
// 如 "abccbaabccbaabccba" → 重复的回文结构
3
struct PalindromeInfo {
4
    int center;
5
    int radius;
6
    std::string palindrome;
7
};
8

9
PalindromeInfo longestPalindrome(const std::string& text) {
10
    // 使用 Manacher 算法（见 9.6 节）
11
    // 返回最长回文及其位置
12
    // 如果回文长度 > 阈值，标记为潜在刷屏
13
    auto result = longestPalindromeManacher(text);
14
    return {0, 0, result};
15
}