Luogu P3375
It has been 423 days since the last update, the content of the article may be outdated.
【模板】KMP
题目描述
给出两个字符串
和 ,若 的区间 子串与 完全相同,则称 在 中出现了,其出现位置为 。 现在请你求出 在 中所有出现的位置。 定义一个字符串
的 border 为 的一个非 本身的子串 ,满足 既是 的前缀,又是 的后缀。 对于 ,你还需要求出对于其每个前缀 的最长 border 的长度。 输入格式
第一行为一个字符串,即为
。 第二行为一个字符串,即为 。 输出格式
首先输出若干行,每行一个整数,按从小到大的顺序输出
在 中出现的位置。 最后一行输出 个整数,第 个整数表示 的长度为 的前缀的最长 border 长度。 样例 #1
样例输入 #1
ABABABC ABA
样例输出 #1
1 3 0 0 1
提示
样例 1 解释
。 对于
长度为 的前缀 ABA
,字符串A
既是其后缀也是其前缀,且是最长的,因此最长 border 长度为。 数据规模与约定
本题采用多测试点捆绑测试,共有 3 个子任务。
- Subtask 1(30 points):
, 。 - Subtask 2(40 points):
, 。 - Subtask 3(30 points):无特殊约定。
对于全部的测试点,保证
, 中均只含大写英文字母。
这道题就是妥妥的KMP模板题,具体原理可以参考知乎Pecco大佬的文章,链接贴上:https://zhuanlan.zhihu.com/p/105629613
需要注意的一点是:Pecco大佬的KMP写法与我所看到的大部分写法有细节上的不同,所以做题的时候,如果打算用Pecco大佬的码作为模板,你需要经常琢磨到底哪一点需要修改,就当是锻炼自己是否真正理解了KMP算法吧。
AC代码
|
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Heavenhold!