Problem1366--KMP字符串模式匹配算法

1366: KMP字符串模式匹配算法

Time Limit: 1 Sec  Memory Limit: 32 MB
Submit: 68  Solved: 39
[Submit] [Status] [Web Board] [Creator:]

Description

KMP算法是字符串模式匹配算法中较为高效的算法之一,其在某次子串匹配母串失败时并未回溯母串的指针而是将子串的指针移动到相应的位置。严蔚敏老师的书中详细描述了KMP算法,同时前面的例子中也描述了子串移动位置的数组实现的算法。前面你已经实现了子串移动的数组,现在就来利用该数组来实现KMP模式匹配。

Input


3组字符串,每组字符串占一行。每行包含由空格分隔的两个字符串,字符串仅由英文小写字母组成且长度不大于100

Output

每组数据输出两行
第一行输出模式串的next数组

第二行输出模式串在母串中的位置,如果不匹配,则输出0

Sample Input

string str
thisisalongstring isa
nosubstring subt

Sample Output

0 1 1
1
0 1 1
5
0 1 1 1
0

HINT


Source/Category