1690 問題 E: 數(shù)據(jù)結(jié)構(gòu)-KMP算法中的模式串移動數(shù)組
時間限制: 1s
內(nèi)存限制: 32MB 提交: 383 解決: 211
題目描述
字符串的子串定位稱為模式匹配，模式匹配可以有多種方法。簡單的算法可以使用兩重嵌套循環(huán)，時間復(fù)雜度為母串與子串長度的乘積。而KMP算法相對來說在時間復(fù)雜度上要好得多，為母串與子串長度的和。但其算符比較難以理解。
在KMP算法中，使用到了一個next數(shù)組。這個數(shù)組就是在比較失配時母串指針不必回溯，而子串指針移動相應(yīng)位置即可。我們給出書中next數(shù)組的算式表示以及算法，請你實現(xiàn)之。
圖1：next數(shù)組的算式表示
圖2：next數(shù)組的算法表示
輸入
一個模式串，僅由英文小寫字母組成。長度不大于100。
輸出
輸出模式串對應(yīng)的移動數(shù)組next。每個整數(shù)后跟一個空格。
樣例輸入
abaabcac
樣例輸出
0 1 1 2 2 3 1 2
提示
比賽公告
大數(shù)乘法, 數(shù)據(jù)結(jié)構(gòu), 字符串, 貪心, 動態(tài)規(guī)劃, 遞歸各一題。
好高興啊, 今天又吃成長快樂啦。