题目描述

作为字符串匹配方法中最难理解的一个算法，就通过这道题再加深一下吧。

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的。其核心为模式串next[]数组的求解，这个算法的高效在于对匹配失败的位置的信息加以了利用。

输入格式

输入为两行

第一行为长度为n的字符串S1；

第二行为长度为m的字符串S2；

1<=n<=1000000;

1<=m<=100000;

m<=n;

输出格式

输出所有S2在S1中出现的起始下标（中间空格隔开） 如果没有匹配项输出“-1”

样例

ababa 
aba 

1 3

提示

by 高晓飞20