【模板】KMP
题目描述
给出两个字符串 s 1和 s 2 ，若 s 1的区间 [ l , r ] 子串与 s 2完全相同，则称 s 2
在 s 1中出现了，其出现位置为 l 。现在请你求出 s 2在 s 1中所有出现的位置。
定义一个字符串 s的 border 为 s 的一个非 s 本身的子串 t，满足 t 既是 s 的前缀，又是 s 的后缀。
对于 s 2，你还需要求出对于其每个前缀 s ′ 的最长 border t ′ 的长度。
输入格式
第一行为一个字符串，即为 s 1。
第二行为一个字符串，即为 s 2 。
输出格式
首先输出若干行，每行一个整数，按从小到大的顺序输出 s 2
在 s 1中出现的位置。
最后一行输出 ∣ s 2 ∣ 个整数，第 i 个整数表示 s 2的长度为 i 的前缀的最长 border 长度。
提示
样例 1 解释
对于 s 2 长度为 3 的前缀 ABA，字符串 A 既是其后缀也是其前缀，且是最长的，因此最长 border 长度为 1。
KMP算法
KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，用于在主字符串（文本）中查找一个子字符串（模式）的出现位置。KMP算法的核心思想是当一次比较失败时，能够利用已经比较过的信息，将模式字符串合理地“滑动”，跳过一些必然不匹配的位置，从而提高匹配效率。
算法步骤
KMP算法主要分为两个步骤：
构建LPS（最长相同前后缀）数组：
LPS数组用于存储模式字符串中每个位置之前字符串的最长相同前后缀的长度。
这个数组是KMP算法的核心，它使得算法能够在匹配失败时知道模式字符串应该如何移动。
使用LPS数组进行字符串匹配：
在主字符串中搜索模式字符串。
如果发生不匹配，利用LPS数组来确定模式字符串的下一个匹配位置，避免从头开始比较。
LPS数组的构建
LPS数组的构建过程如下：
初始化LPS数组，长度与模式字符串相同，并将第一个元素设置为0。
使用两个指针i和j，其中i是当前正在计算LPS值的模式字符串的位置，j是当前最长相等前后缀的长度。
遍历模式字符串，对于每个位置i：
如果模式字符串在i和j位置的字符相同，则LPS[i] = j + 1，并将j加1。
如果不相同，则将j设置为LPS[j – 1]（这是利用已经计算出的LPS值来找到下一个可能的匹配位置）。
如果j为0，则LPS[i] = 0。
匹配过程
匹配过程如下：
使用两个指针，一个在主字符串上（i），一个在模式字符串上（j）。
逐个字符比较i和j位置的字符：
如果字符匹配，则两个指针都向前移动一位。
如果j达到了模式字符串的末尾，说明找到了一个匹配，记录下匹配的位置，并将j设置为LPS[j – 1]（如果需要继续查找下一个匹配）。
如果字符不匹配，则将j设置为LPS[j – 1]，这样可以跳过一些必然不匹配的位置。
时间复杂度
KMP算法的时间复杂度是O(n + m)，其中n是主字符串的长度，m是模式字符串的长度。这是因为LPS数组只需要O(m)时间构建，而匹配过程也是O(n)。
优点
KMP算法相比于朴素的字符串匹配算法（时间复杂度为O(n*m)）有以下几个优点：
不需要回溯主字符串的指针。
在最坏情况下仍然保持线性时间复杂度。
通过预处理的LPS数组，减少了不必要的比较。
KMP算法广泛应用于文本编辑器中的查找替换功能、字符串搜索算法以及各种需要高效字符串匹配的场景。
代码实现
include
using namespace std;
// KMP类用于实现KMP字符串匹配算法
class KMP
{
private:
// lps数组用于存储每个位置的最长相同前后缀长度
vector lps;
// pattern存储要匹配的模式字符串
string pattern;
// init函数用于初始化lps数组
void init(string &s)
{
// lps的第一个值总是0
lps[0] = 0;
int n = s.size();
// 遍历模式字符串，计算lps数组
for (int i = 1; i < n; i++)
{
int j = lps[i - 1];
// 如果当前字符不匹配，回退到上一个lps值
while (j > 0 && s[i] != s[j])
{
j = lps[j - 1];
}
// 更新lps值
lps[i] = j + (s[i] == s[j]);
}
// 保存模式字符串
this->pattern = s;
}
public:
// 构造函数，接收模式字符串并初始化lps数组
KMP(string &pattern)
{
lps.resize(pattern.size());
init(pattern);
}
// find函数用于在文本中查找模式字符串的所有出现位置
vector<int> find(string &text)
{
vector<int> v; // 存储匹配位置
int pos = 0; // 当前匹配的位置
for (int i = 0; i < text.size(); i++)
{
// 如果字符不匹配，回退到上一个lps值
while (pos > 0 && text[i] != pattern[pos])
{
pos = lps[pos-1];
}
// 如果字符匹配，移动到下一个位置
if (text[i] == pattern[pos])
pos++;
// 如果模式字符串完全匹配，记录位置
if (pos == pattern.size())
{
v.push_back(i+1 - int(pattern.size()) + 1); // 记录匹配开始的位置
pos = lps[pos-1]; // 回退到上一个lps值，继续查找
}
}
return v;
}
// print_lps函数用于打印lps数组
void print_lps(){
for(int i=0;i+1<pattern.size();i++){
cout<<lps[i]<<' ';
}
cout<<lps.back(); // 打印最后一个lps值
}
};
int main()
{
ios::sync_with_stdio(false); // 关闭C++与C的同步，提高输入输出效率
cin.tie(0); // 解除cin与cout的绑定，提高输入输出效率
cout.tie(0); // 解除cout与cin的绑定，提高输入输出效率
string s1, s2; // s1为文本字符串，s2为模式字符串
cin >> s1 >> s2; // 从标准输入读取文本字符串和模式字符串
// 创建KMP对象
auto kmp = KMP(s2);
// 在文本中查找模式字符串的所有出现位置
auto res = kmp.find(s1);
// 打印所有匹配位置
for (auto &pos : res) {
cout << pos << endl;
}
// 打印lps数组
kmp.print_lps();
return 0;
}
————————————————
