flâneur

初學者學 KMP 演算法 | Yeefun

yeefun.github.io · 1,221 words · saved by 1 readers

一個初學者看得懂的 KMP 演算法。

初學者學 KMP 演算法 | Yeefun 初學者學 KMP 演算法 2020-12-22 ( Last updated: 2020-12-27 ) · #algorithm #string #kmp KMP 算法 Next 表 那些長得不太一樣的 Next 表 相關資料 第一次碰 KMP，被搞得暈頭轉向，花了兩天才搞定。只好趕緊寫下來，以免半小時後就忘記。 要怎麼在主串裡找到某個子串（模式）呢？ 比如 abcabcabe 是主串，要怎麼找到 abcabe 這個子串？ 最簡單的想法，就是從主串的第一個字跟子串的第一個字開始比，如果第一個字相同，再接著比第二個字，若第二個字也相同，再接著比第三個字⋯⋯如果不同，則主串回到第二個字、子串回到第一個字，接著主串的第二個字跟子串的第一個字比，如果相同，則主串的第三個字跟子串的第二個字比；如果不同，則主串回到第三個字，子串回到第一個字⋯⋯以此類推。 用程式碼表示就是這樣： function indexOfByBf ( s , p ) { let sI = 0 ; let pI = 0 ; while ( sI < s . length && pI < p . length ) { if ( s [ sI ] === p [ pI ] ) { sI += 1 ; pI += 1 ; } else { sI = sI - pI + 1 ; pI

related reading