1690 問題 H: 數(shù)據(jù)結構-KMP算法中的模式串移動數(shù)組
時間限制: 1s
內(nèi)存限制: 32MB 提交: 383 解決: 211
題目描述
字符串的子串定位稱為模式匹配，模式匹配可以有多種方法。簡單的算法可以使用兩重嵌套循環(huán)，時間復雜度為母串與子串長度的乘積。而KMP算法相對來說在時間復雜度上要好得多，為母串與子串長度的和。但其算符比較難以理解。
在KMP算法中，使用到了一個next數(shù)組。這個數(shù)組就是在比較失配時母串指針不必回溯，而子串指針移動相應位置即可。我們給出書中next數(shù)組的算式表示以及算法，請你實現(xiàn)之。
圖1：next數(shù)組的算式表示
圖2：next數(shù)組的算法表示
輸入
一個模式串，僅由英文小寫字母組成。長度不大于100。
輸出
輸出模式串對應的移動數(shù)組next。每個整數(shù)后跟一個空格。
樣例輸入
abaabcac
樣例輸出
0 1 1 2 2 3 1 2
比賽公告
話不多說，我就是湊字數(shù)?？ü∴?/p>