題目 1690:
數(shù)據(jù)結(jié)構(gòu)-KMP算法中的模式串移動(dòng)數(shù)組
時(shí)間限制: 2s
內(nèi)存限制: 96MB 提交: 383 解決: 211
題目描述
字符串的子串定位稱為模式匹配，模式匹配可以有多種方法。簡(jiǎn)單的算法可以使用兩重嵌套循環(huán)，時(shí)間復(fù)雜度為母串與子串長(zhǎng)度的乘積。而KMP算法相對(duì)來(lái)說(shuō)在時(shí)間復(fù)雜度上要好得多，為母串與子串長(zhǎng)度的和。但其算符比較難以理解。
在KMP算法中，使用到了一個(gè)next數(shù)組。這個(gè)數(shù)組就是在比較失配時(shí)母串指針不必回溯，而子串指針移動(dòng)相應(yīng)位置即可。我們給出書中next數(shù)組的算式表示以及算法，請(qǐng)你實(shí)現(xiàn)之。
圖1：next數(shù)組的算式表示
圖2：next數(shù)組的算法表示
輸入格式
一個(gè)模式串，僅由英文小寫字母組成。長(zhǎng)度不大于100。
輸出格式
輸出模式串對(duì)應(yīng)的移動(dòng)數(shù)組next。每個(gè)整數(shù)后跟一個(gè)空格。
樣例輸入
abaabcac
樣例輸出
0 1 1 2 2 3 1 2
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情