|
Der KMP-Algorithmus (Knuth-Morris-Pratt-Algorithmus) wird für den String-Abgleich verwendet, um einen bestimmten Teilstring aus einem String zu finden. Aber es ist nicht ganz einfach, es zu verstehen und zu meistern. Das Verständnis der partiellen Matching-Tabelle in ihrem Konzept ist der Schlüssel zum Verständnis des KMP-Algorithmus. Die Diskussion hier vermeidet die obskure Logik dahinter und konzentriert sich darauf, sie anhand ihrer Anwendung zu verstehen. String-SucheSuchen Sie beispielsweise die Teilzeichenfolge Eine einfache Lösung:
Der Nachteil dieser einfachen Lösung besteht darin, dass sich der Index jedes Mal, wenn die Übereinstimmung fehlschlägt, nur um eine Position zurückbewegt, was viele redundante Vorgänge mit sich bringt und nicht effizient ist. In der ersten Matching-Runde, also wenn der Index 0 ist, können wir feststellen, dass die ersten vier Zeichen Partielle Übereinstimmungstabelle/Partielle Übereinstimmungstabelle Nehmen wir als Beispiel eine Zeichenfolge der Länge 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> Nach dem Login kopieren Nach dem Login kopieren Die Zeile TeilmengeWenn wir für die obige Beispielzeichenfolge die Position beobachten, an der Präfix und SuffixEntfernen Sie für eine bestimmte Zeichenfolge ein oder mehrere Zeichen vom Ende, und der verbleibende Teil wird als wahrer Wert des Zeichenfolgenpräfixes (Proper) bezeichnet Präfix), im Folgenden Präfix genannt. „Wahr“ bedeutet hier nicht „wahres Präfix“. Denken Sie an die „eigentliche Teilmenge“ einer Menge in der Mathematik. Beispielsweise lautet das Präfix
In ähnlicher Weise entfernen Sie ausgehend von der Kopfzeile ein oder mehrere Wörter, und der verbleibende Teil ist das wahre Suffix (richtiges Suffix) der Zeichenfolge. Oder
Teilweiser ÜbereinstimmungswertEs ist ersichtlich, dass alle Präfixe und Suffixe mengenmäßig symmetrisch sind. Dann können wir eines aus dem Präfix finden und es mit dem Suffix abgleichen Der Sinn dieser Verbindung ist mir egal. Nehmen Sie als Beispiel den Anfangstext Wenn wir die Position beobachten, an der
Passen Sie die Präfixe im Suffix der Reihe nach an. Das einzige Unterzeichen, das in der Suffixliste übereinstimmen kann, ist Sehen Sie sich als weiteres Beispiel die Position an, an der
Zu diesem Zeitpunkt kann es beobachtet werden dass das übereinstimmende Element Beobachten wir als weiteres Beispiel die Position, an der
dann nimm Jedes Element im Präfix wird mit dem Element im Suffix abgeglichen und schließlich werden zwei passende Elemente gefunden,
Wir nehmen die längere Schauen wir uns nun die obige Teilübereinstimmungstabelle an. Erstens können wir verstehen, woher ihr Wert kommt, und zweitens können wir die Bedeutung ihrer Darstellung verstehen, d. h. die längste Länge unter allen Übereinstimmungen von Präfixen und Suffixen. Wenn wir fortfahren, bis Wenn Sie fortfahren, erreichen Sie das Ende der Zeichenfolge, also die gesamte Zeichenfolge Verwendung einer teilweisen ÜbereinstimmungstabelleWenn wir den oben genannten Wert für die teilweise Übereinstimmung verwenden, müssen wir bei der Durchführung einer Zeichenfolgensuche nicht nach jedem Fehler nur ein Bit verschieben. Es können jedoch mehrere Bits verschoben werden, um einige redundante Übereinstimmungen zu entfernen. Hier gibt es eine Formel wie folgt:
如果匹配过程中，匹配到了部分值为 下面是本文开始时的那个部分匹配表: <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> Nach dem Login kopieren Nach dem Login kopieren 假设需要从 首次匹配发生在总字符串的第二个字符， <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">bacbababaabcbab |<br> abababca</span> Nach dem Login kopieren 此时匹配的长度为 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> Nach dem Login kopieren 现在匹配到的长度是 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> Nach dem Login kopieren 此时匹配到的长度为 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> Nach dem Login kopieren 此时我们需要查找的字符串其长度已经超出剩余可用来匹配的字符串了，所以可直接结束匹配，得到结论：没有查找到结果。 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>Nach dem Login kopieren 时间复杂度 因为算法中涉及两部分字符串的线性对比，其时间复杂度为两字符串长度之和，假设需要搜索的关键词长度为 k，总字符串长度为 m，则时间复杂度为 O(k+m)。 |
Das obige ist der detaillierte Inhalt vonDamit Sie den KMP-Algorithmus leicht verstehen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
