字符串
约 979 字大约 3 分钟
2026-01-23
警告
本模板为了便于理解,包含了大量的详细注释以及规范的 std:: 命名空间前缀。在您将代码复制并提交至相关竞赛或评测平台前,请务必根据个人的编程习惯进行调整,重点建议删除冗余注释并精简代码风格。保留明显的模板特征极易被系统的查重算法或 AIGC 监测机制误标为“人工智能生成内容”,从而对您的评审进度或最终成绩产生不利影响。
前缀函数(KMP)
给定一个长度为 n 的字符串 s,其前缀函数被定义为一个长度为 n 的数组 π。其中 π[i] 的定义是:
- 如果子串 s[0…i] 有一对相等的真前缀与真后缀:s[0…k−1] 和 s[i−(k−1)…i],那么 π[i] 就是这个相等的真前缀(或者真后缀,因为它们相等)的长度,也就是 π[i]=k;
- 如果不止有一对相等的,那么 π[i] 就是其中最长的那一对的长度;
- 如果没有相等的,那么 π[i]=0。
简单来说 π[i] 就是,子串 s[0…i] 最长的相等的真前缀与真后缀的长度,下面的算法在 OI-WIKI 上证明复杂度为 O(n)
提示
「你真要用到字符串匹配,直接 str.find() 省时省力,比你 Knuth - Morris - Pratt 还有 Boyer - Moore 什么算法花里胡哨的快得多甚至,所以一般不会用于字符串匹配。」
kmp.cc
#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)
提示
个人感觉 Trie 没啥吊用。
trie.cc
// 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;
}