#P1178. KMP字符串

KMP字符串

题目描述:

给定一个模式串 S,以及一个模板串 P,所有字符串中只包含大小写英文字母以及阿拉伯数字。模板串 P在模式串 S中多次作为子串出现。

求出模板串 P在模式串 S 中所有出现的位置的起始下标。

输入格式:

第一行输入整数 N,表示字符串 P的长度。第二行输入字符串 P

第三行输入整数 M,表示字符串 S的长度。

第四行输入字符串 S

输出格式:

共一行,输出所有出现位置的起始下标(下标从 0 开始计数),整数之间用空格隔开,如果没有找到输出-1。

数据范围:

1≤N≤1e5 1≤M≤1e6

3
aba
5
ababa
0 2