---
url: /algo/2nqqafx6/index.md
---
::: warning 警告
本模板为了便于理解，包含了大量的详细注释以及规范的 `std::` 命名空间前缀。在您将代码复制并提交至相关竞赛或评测平台前，请务必根据个人的编程习惯进行调整，重点建议删除冗余注释并精简代码风格。保留明显的模板特征极易被系统的查重算法或 AIGC 监测机制误标为“人工智能生成内容”，从而对您的评审进度或最终成绩产生不利影响。
:::

## 前缀函数(KMP)

给定一个长度为 $n$ 的字符串 $s$，其前缀函数被定义为一个长度为 $n$ 的数组 $\pi$。其中 $\pi\[i]$ 的定义是：

1. 如果子串 $s\[0\dots i]$ 有一对相等的真前缀与真后缀：$s\[0\dots k-1]$ 和 $s\[i - (k - 1) \dots i]$，那么 $\pi\[i]$ 就是这个相等的真前缀（或者真后缀，因为它们相等）的长度，也就是 $\pi\[i]=k$；
2. 如果不止有一对相等的，那么 $\pi\[i]$ 就是其中最长的那一对的长度；
3. 如果没有相等的，那么 $\pi\[i]=0$。

简单来说 $\pi\[i]$ 就是，子串 $s\[0\dots i]$ 最长的相等的真前缀与真后缀的长度，下面的算法在 OI-WIKI 上证明复杂度为 $O(n)$

::: tip
「你真要用到字符串匹配，直接 `str.find()` 省时省力，比你 Knuth - Morris - Pratt 还有 Boyer - Moore 什么算法花里胡哨的快得多甚至，所以一般不会用于字符串匹配。」
:::

```cpp title="kmp.cc" :collapsed-lines
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// kmp 1-base
std::vector<int> kmp(std::string s)
{
    int n = s.size();
    std::vector<int> f(n + 1);
    for (int i = 1, j = 0; i < n; i++)
    {
        while (j && s[i] != s[j])
        {
            j = f[j];
        }
        j += (s[i] == s[j]);
        f[i + 1] = j;
    }
    return f;
}

vector<int> prefix_function(string s)
{
    int n = (int)s.length();
    vector<int> pi(n);
    for (int i = 1; i < n; i++)
    {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j])
            j = pi[j - 1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}

// 或者直接用 find_occurrences 封装度高

vector<int> find_occurrences(string text, string pattern)
{
    string cur = pattern + '#' + text;
    int sz1 = text.size(), sz2 = pattern.size();
    vector<int> v;
    vector<int> lps = prefix_function(cur);
    for (int i = sz2 + 1; i <= sz1 + sz2; i++)
    {
        if (lps[i] == sz2)
            v.push_back(i - 2 * sz2);
    }
    return v;
}

// 朴素 0-base O(n)

vector<int> stringPi(string pattern)
{
    vector<int> pattern_pi(pattern.size());

    for (int i = 1; i < pattern_pi.size(); i++)
    {
        int len = pattern_pi[i - 1];
        while (len != 0 && pattern[i] != pattern[len])
        {
            len = pattern_pi[len - 1];
        }
        if (pattern[i] == pattern[len])
        {
            pattern_pi[i] = len + 1;
        }
    }
    return pattern_pi;
}

// 使用方法：查找 pattern 在 source 中的位置

int main()
{
    string source, pattern;
    cin >> source >> pattern;
    string fs = pattern + "#" + source;
    int len = pattern.size();
    auto fspi = kmp(fs);
    for (int i = 1; i < fspi.size(); i++)
    {
        if (fspi[i] == len)
        {
            cout << i - len * 2 << "\n";
        }
        // cout << fspi[i] << " ";
    }
    auto pattpi = kmp(pattern);

    for (int i = 1; i < pattpi.size(); i++)
    {
        cout << pattpi[i] << " ";
    }

    return 0;
}
```

## 字典树(Trie)

::: tip
个人感觉 Trie 没啥吊用。
:::

```cpp title="trie.cc" :collapsed-lines
// https://www.luogu.com.cn/record/233659410
// By Timothy Starman 2025-08-29 10:38:42 
#include <bits/stdc++.h>
using namespace std;

class TrieTree
{
public:
    int id;
    char s = 0;
    bool isrep = false;
    vector<TrieTree *> vt;
    vector<char> vc;
    bool isWordEnd = false;
};
void TrieTreeInsert(TrieTree &root, string s)
{
    int sons = root.vc.size();
    TrieTree *currentNode = &root;
    int notFindIndex = 0;
    bool allfind = true;
    for (int i = 0; i < s.size(); i++)
    {
        auto iter = find(currentNode->vc.begin(), currentNode->vc.end(), s[i]);
        if (iter == currentNode->vc.end())
        {
            notFindIndex = i;
            allfind = false;
            break;
        }
        int index = iter - currentNode->vc.begin();
        currentNode = currentNode->vt[index];
        if (i == s.size() - 1)
        {
            currentNode->isWordEnd = true;
        }
    }
    if (allfind == false)
    {
        for (int j = notFindIndex; j < s.size(); j++)
        {
            TrieTree *newTree = new TrieTree;
            newTree->s = s[j];
            currentNode->vt.push_back(newTree);
            currentNode->vc.push_back(s[j]);
            currentNode = newTree;
            if (j == s.size() - 1)
            {
                currentNode->isWordEnd = true;
            }
        }
    }
}
string TrieTreeQuery(TrieTree &root, string s)
{
    int sons = root.vc.size();
    TrieTree *currentNode = &root;
    int notFindIndex = 0;
    bool allfind = true;
    for (int i = 0; i < s.size(); i++)
    {
        auto iter = find(currentNode->vc.begin(), currentNode->vc.end(), s[i]);
        if (iter == currentNode->vc.end())
        {
            notFindIndex = i;
            allfind = false;
            return "WRONG";
        }
        int index = iter - currentNode->vc.begin();
        currentNode = currentNode->vt[index];
        if (i == s.size() - 1 && currentNode->isWordEnd == true && currentNode->isrep == false)
        {
            currentNode->isrep = true;
            return "OK";
        }
        else if (i == s.size() - 1 && currentNode->isWordEnd == false)
        {
            return "WRONG";
        }
        else if (i == s.size() - 1 && currentNode->isrep == true)
        {
            return "REPEAT";
        }
    }
    return "WRONG";
}
int main()
{

    int t;
    cin >> t;
    TrieTree root;
    for (int i = 0; i < t; i++)
    {
        string s;
        cin >> s;
        TrieTreeInsert(root, s);
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; i++)
    {
        string s;
        cin >> s;
        cout << TrieTreeQuery(root, s) <<"\n";
    }

    return 0;
}
```