KMP算法是字符串模式匹配算法中較為高效的算法之一，其在某次子串匹配母串失敗時(shí)并未回溯母串的指針而是將子串的指針移動(dòng)到相應(yīng)的位置。嚴(yán)蔚敏老師的書(shū)中詳細(xì)描述了KMP算法，同時(shí)前面的例子中也描述了子串移動(dòng)位置的數(shù)組實(shí)現(xiàn)的算法。前面你已經(jīng)實(shí)現(xiàn)了子串移動(dòng)的數(shù)組，現(xiàn)在就來(lái)利用該數(shù)組來(lái)實(shí)現(xiàn)KMP模式匹配。

下面是相應(yīng)的算法：

圖：KMP算法

3組字符串，每組字符串占一行。每行包含由空格分隔的兩個(gè)字符串，字符串僅由英文小寫(xiě)字母組成且長(zhǎng)度不大于100。

每組數(shù)據(jù)輸出1行，輸出后一個(gè)字符串在前一個(gè)字符串中的位置，如果不匹配，則輸出0。

string str
thisisalongstring isa
nosubstring subt

1
5
0