2037: KMP字符串模式匹配算法实现

Memory Limit：32 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：11 Solved：8

Description


KMP算法是字符串模式匹配算法中较为高效的算法之一，其在某次子串匹配母串失败时并未回溯母串的指针而是将子串的指针移动到相应的位置。前面你已经实现了子串移动的数组，现在就来利用该数组来实现KMP模式匹配。



Input


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

Output

每组数据输出1行，输出后一个字符串在前一个字符串中的位置，如果不匹配，则输出0。

Sample Input Copy 

string str
thisisalongstring isa
nosubstring subt

Sample Output Copy 

1
5
0

HINT



Source/Category