洛谷P3375 【模板】KMP字符串匹配
题目大意
给定两个字符串 s1s1 和 s2s2，要求输出 s2s2 在 s1s1 中所有出现的位置（起始下标），并输出 s2s2 的每个前缀的最长 border 长度。
数据范围： ∣s1∣,∣s2∣≤1e6∣s1∣,∣s2∣≤1e6 。
一般思路
我们很容易想到的就是匹配字符串时，我们从目标字符串 长度为 n 的 s1 的第一个下标选取和长度为 m 的 s2 长度一样的子字符串进行比较，如果一样，就返回开始处的下标值，不一样，选取 s1 下一个下标，同样从 s2 选取长度为 n 的字符串进行比较，直到 s1 的末尾。
显然，我们发现了许多不合理的操作：比对失败时会从头开始匹配，浪费了许多时间，时间复杂度为 O(nm)。
分析
问题为经典的多模式串匹配问题，需要在线性时间内完成。
KMP（Knuth-Morris-Pratt）算法通过预处理模式串的 next 数组（即每个前缀的最长 border），在匹配时利用已匹配信息避免回溯，达到 O(∣s1∣+∣s2∣)O(∣s1∣+∣s2∣) 的时间复杂度。
border 定义：对于一个字符串 ss，它的一个非本身的前缀同时也是后缀，称为 border。最长 border 即最长的这样的前缀（也是后缀）。
然后我们就可以借助border进行跳跃，不需要再从头匹配
Solution
标签： 字符串，KMP
算法思路
- 预处理 next 数组（代码中为 kmp 数组）：
对于模式串 s2（下标从 1 开始），kmp[i] 表示长度为 i 的前缀的最长 border 长度。
通过双指针 i 和 j 递推得到：
初始化 j = 0，kmp[1] = 0（长度为 1 的前缀无 border）。
对于 i = 2 到 len2，当 j > 0 且当前字符不匹配时，j = kmp[j] 回退；若匹配则 j++，然后 kmp[i] = j。
2. 匹配过程：
在文本串 s1s1 上同样用双指针 i 和 j 进行匹配。
i 遍历文本串，j 表示当前已匹配的模式串长度。
当字符不匹配时，j = kmp[j] 回退。
若匹配则 j++，当 j == len2 时说明找到一个匹配，输出起始位置 i - len2 + 1，然后 j = kmp[j] 继续寻找下一个匹配。
3. 输出结果：
先输出所有匹配位置（每行一个），最后输出一行 len2 个整数，即 kmp[1] 到 kmp[len2]。
代码说明
为方便处理，在字符串前加了一个空格，使得下标从 1 开始，避免下标转换。
vectorkmp(len2 + 1) 存储 next 数组。
预处理和匹配过程均使用 while 循环处理失配回退。
注意输出格式：匹配位置每行一个，最后一行 border 长度用空格隔开。
时间复杂度
预处理 O(∣s2∣)O(∣s2∣)，匹配 O(∣s1∣)O(∣s1∣)，总复杂度线性，可处理大规模数据。
下面是代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define fast ios::sync_with_stdio(0),cin.tie(0)
#define pll pair<ll,ll>void solve(){string s1,s2;cin >> s1 >> s2;s1 = " " + s1;s2 = " " + s2;ll len1 = s1.size() - 1;ll len2 = s2.size() - 1;vector<ll> kmp(len2 + 1);for(ll i = 2, j = 0; i <= len2; i++){while(j && s2[i] != s2[j + 1]) j = kmp[j];if(s2[i] == s2[j + 1]) j++;kmp[i] = j;}for(ll i = 1, j = 0; i <= len1; i++){while(j && s1[i] != s2[j + 1]) j = kmp[j];//可以的话就过了，否则会变成0if(s1[i] == s2[j + 1]) j++;if(j == len2){cout<<i - len2 + 1<<endl;j = kmp[j];}}for(ll i = 1; i <= len2; i++){cout<<kmp[i]<<" ";}return;
}int main(){fast;ll t = 1; //cin >> t;while(t--){solve();}return 0;
}