3513. kmp模板

【题目描述】

给出两个字符串 $s_1$ 和 $s_2$，若 $s_1$ 的区间 $[l,r]$ 子串与 $s_2$ 完全相同，则称 $s_2$ 在 $s_1$ 中出现了，其出现位置为 $l$。

现在请你求出 $s_2$ 在 $s_1$ 中所有出现的位置。

定义一个字符串 $s$ 的 $border$ 为 $s$ 的一个非 $s$ 本身的子串 $t$，满足 $t$ 既是 $s$ 的前缀，又是 $s$ 的后缀。

对于 $s_2$，你还需要求出对于其每个前缀 $s$′ 的最长 $border$ $t$′ 的长度。

【输入格式】

第一行是$s_1$，第二行是$s_2$;

【输出格式】

首先输出若干行，每行一个整数，按从小到大的顺序输出 $s_2$ 在 $s_1$ 中出现的位置。

最后一行输出 ∣$s_2$∣ 个整数，第 $i$ 个整数表示 $s_2$ 的长度为 $i$ 的前缀的最长 $border$ 长度。

【样例输入】

ABABABC
ABA

【样例输出】

1
3
0 0 1

【数据规模与约定】

对于全部的测试点，保证$s_1.len$,$s_2.len<10^6+20$,$s_1$,$s_2$ 中均只含大写英文字母。

【来源】

$lg$