3375

题目传送门 思路： 首先我们要学习一下 \(KMP\) 算法，不会的可以看这个大佬的文章 那么我们就直接开始讲思路了。 针对于每一位，\(kmp\) 算法已经预处理出了一个对应 \(kmp\) 数组的单元，映射着如果此位失配，它可能的最靠后的一个重新开头是哪一个。 让我们举一个例子：假如让 \(aa ......

1 #include <bits/stdc++.h> 2 using namespace std; 3 string s1, s2; 4 vector<int> find_next(vector<int> next, string s) 5 { 6 int i = 1, prefix = 0, le ......

前言 狗屁不是，建议别看！！！ 题目链接 P3375 【模板】KMP 字符串匹配 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 分析 先给个例子 s1：ABCABCABB s2：ABCABB 若使用朴素算法匹配，当匹配到 s1：ABCAB C ABB s2：ABCAB B 时，朴 ......

# 【模板】KMP字符串匹配 ## 题目描述 给出两个字符串 $s_1$ 和 $s_2$，若 $s_1$ 的区间 $[l, r]$ 子串与 $s_2$ 完全相同，则称 $s_2$ 在 $s_1$ 中出现了，其出现位置为 $l$。 现在请你求出 $s_2$ 在 $s_1$ 中所有出现的位置。 定义一个 ......