#P3043. 【模板】KMP字符串匹配

【模板】KMP字符串匹配

题目描述

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

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

输入格式

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

输出格式

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

ABABABC
ABA

1
3
0 0 1 

提示

样例 1 解释

对于 s2s_2 长度为 33 的前缀 ABA,字符串 A 既是其后缀也是其前缀,且是最长的,因此最长 border 长度为 11

数据规模与约定

本题采用多测试点捆绑测试,共有 3 个子任务

  • Subtask 1(30 points):s115|s_1| \leq 15s25|s_2| \leq 5
  • Subtask 2(40 points):s1104|s_1| \leq 10^4s2102|s_2| \leq 10^2
  • Subtask 3(30 points):无特殊约定。

对于全部的测试点,保证 1s1,s21061 \leq |s_1|,|s_2| \leq 10^6s1,s2s_1, s_2 中均只含大写英文字母。