#926. 【模板】KMP

【模板】KMP

题目描述

给出两个字符串 s1s_1 和 s2s_2,若 s1s_1 的区间 [l,r][l, r] 子串与 s2s_2 完全相同,则称 s2s_2 在 s1s_1 中出现了,其出现位置为 ll。
现在请你求出 s2s_2 在 s1s_1 中所有出现的位置。

定义一个字符串 ss 的 border 为 ss 的一个非 ss 本身的子串 tt,满足 tt 既是 ss 的前缀,又是 ss 的后缀。
对于 s2s_2,你还需要求出对于其每个前缀 s′s' 的最长 border t′t' 的长度。

输入格式

第一行为一个字符串,即为 s1s_1。
第二行为一个字符串,即为 s2s_2。

输出格式

首先输出若干行,每行一个整数,按从小到大的顺序输出 s2s_2 在 s1s_1 中出现的位置。
最后一行输出 ∣s2∣|s_2| 个整数,第 ii 个整数表示 s2s_2 的长度为 ii 的前缀的最长 border 长度。

样例

ABABABC
ABA
1
3
0 0 1 

题目来源:洛谷 P3375