#P3043. 【模板】KMP字符串匹配
【模板】KMP字符串匹配
题目描述
给出两个字符串 和 ,若 的区间 子串与 完全相同,则称 在 中出现了,其出现位置为 。
现在请你求出 在 中所有出现的位置。
定义一个字符串 的 border 为 的一个非 本身的子串 ,满足 既是 的前缀,又是 的后缀。
对于 ,你还需要求出对于其每个前缀 的最长 border 的长度。
输入格式
第一行为一个字符串,即为 。
第二行为一个字符串,即为 。
输出格式
首先输出若干行,每行一个整数,按从小到大的顺序输出 在 中出现的位置。
最后一行输出 个整数,第 个整数表示 的长度为 的前缀的最长 border 长度。
ABABABC
ABA
1
3
0 0 1
提示
样例 1 解释
。
对于 长度为 的前缀 ABA
,字符串 A
既是其后缀也是其前缀,且是最长的,因此最长 border 长度为 。
数据规模与约定
本题采用多测试点捆绑测试,共有 3 个子任务。
- Subtask 1(30 points):,。
- Subtask 2(40 points):,。
- Subtask 3(30 points):无特殊约定。
对于全部的测试点,保证 , 中均只含大写英文字母。