KMP(The Knuth-Morris-Pratt Algorithm)演算法用於字串匹配,從字串中找出給定的子字串。但它並不是很好理解和掌握。而理解它概念中的部分匹配表,是理解 KMP 演算法的關鍵。 這裡的討論繞過其背後晦澀難懂的邏輯,著重從其運用上來理解它。 字串尋找例如從字串 樸素的解法,我們可以這樣做,
這種樸素解法的弊端在於,每次匹配失敗,索引只後移一位,有很多冗餘操作,效率不高。 在進行第一輪匹配中,即索引為0 時,我們能夠匹配出前四個字元 部分符合表格/Partial Match Table以長度為8 的字串 <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">char: | a | b | a | b | a | b | c | a |<br>index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | <br>value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |</span> 其中 子集對於上面範例字串,假如我們觀察到第 前綴& 後綴對於給定的字串,從末尾開始去掉一個或多個字符,剩下的部分都叫作該字串的真前綴(Proper prefix),後面簡稱前綴。這裡「真」不是「真·前綴」的意思,聯想數學裡面集合的「真子集」。例如
同理,從首部開始,去掉一個或多個字條,剩下的部分是該字串的真後綴(Proper suffix)。還是
,
bab b
bab ,
abababc c 的只有abababc,而該長度7 與同等長度的後綴bababca 不符。至此就可以得出結論,配對結果就是 1,沒有更長的匹配了。
如果匹配过程中,匹配到了部分值为 下面是本文开始时的那个部分匹配表: <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">char: | a | b | a | b | a | b | c | a |<br>index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | <br>value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |</span> 假设需要从 首次匹配发生在总字符串的第二个字符, <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">bacbababaabcbab |<br> abababca</span> 此时匹配的长度为 1,部分匹配表中索引为 1-1=0 的位置对应的部分匹配值为 0,所以我们可以向前移动的距离是 继续直到再次发生匹配,此时匹配到的情况如下: <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">bacbababaabcbab |||||<br> abababca</span> 现在匹配到的长度是 5,部分匹配表中 5-1=4 对应的部分匹配值为 3,所以我们可以向前移动 5-3=2,此时一下子就可以移动两位了。 <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif"> 上一次的位置 | 最新移动到的位置 | |bacbababaabcbab<br> xx|||<br> abababca</span> 此时匹配到的长度为 3, 查找到 3-1=2。 <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">bacbababaabcbab<br> xx|<br> abababca</span> 此时我们需要查找的字符串其长度已经超出剩余可用来匹配的字符串了,所以可直接结束匹配,得到结论:没有查找到结果。 Javascript 中的实现以下是来自 trekhleb/javascript-algorithms 中 JavaScript 版本的 KMP 算法实现: 相关教程:Javascript视频教程 <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">//**<br/> * @see https://www.youtube.com/watch?v=GTJr8OvyEVQ<br/> * @param {string} word<br/> * @return {number[]}<br/> */<br/>function buildPatternTable(word) {<br/> const patternTable = [0];<br/> let prefixIndex = 0;<br/> let suffixIndex = 1;<br/><br/> while (suffixIndex < word.length) {<br/> if (word[prefixIndex] === word[suffixIndex]) {<br/> patternTable[suffixIndex] = prefixIndex + 1;<br/> suffixIndex += 1;<br/> prefixIndex += 1;<br/> } else if (prefixIndex === 0) {<br/> patternTable[suffixIndex] = 0;<br/> suffixIndex += 1;</span><span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif"><br/></span><span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif"> } else {<br/> prefixIndex = patternTable[prefixIndex - 1];<br/> }<br/> }<br/><br/> return patternTable;<br/>}<br/><br/>/**<br/> * @param {string} text<br/> * @param {string} word<br/> * @return {number}<br/> */<br/>export default function knuthMorrisPratt(text, word) {<br/> if (word.length === 0) {<br/> return 0;</span><span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif"><br/> }<br/><br/> let textIndex = 0;<br/> let wordIndex = 0;<br/><br/> const patternTable = buildPatternTable(word);<br/><br/> while (textIndex < text.length) {<br/> if (text[textIndex] === word[wordIndex]) {<br/> // We've found a match.<br/> if (wordIndex === word.length - 1) {<br/> return (textIndex - word.length) + 1;<br/> }<br/> wordIndex += 1;<br/> textIndex += 1;<br/> } else if (wordIndex > 0) {<br/> wordIndex = patternTable[wordIndex - 1];<br/> } else {<br/> wordIndex = 0;<br/> textIndex += 1;<br/> }<br/> }<br/><br/> return -1;<br/>}<br/></span> 时间复杂度 因为算法中涉及两部分字符串的线性对比,其时间复杂度为两字符串长度之和,假设需要搜索的关键词长度为 k,总字符串长度为 m,则时间复杂度为 O(k+m)。 |
以上是帶你輕鬆理解KMP演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章!