|
KMP(Knuth-Morris-Pratt 알고리즘) 알고리즘은 문자열 일치에 사용되어 문자열에서 특정 하위 문자열을 찾습니다. 하지만 이해하고 익히기가 쉽지 않습니다. 부분 매칭 테이블의 개념을 이해하는 것이 KMP 알고리즘을 이해하는 열쇠입니다. 여기서 논의는 모호한 논리를 피하고 적용을 통해 이해하는 데 중점을 둡니다. String search예를 들어 문자열 朴素的解法，我们可以这样做，
这种朴素解法的弊端在于，每次匹配失败，索引只后移一位，有很多冗余操作，效率不高。 在进行第一轮匹配中，即索引为 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）。还是
abcd가 동일한지 매칭한 다음 원하는 g 는 실제 e와 일치하지 않습니다. 이는 인덱스가 0일 때 일치가 실패했음을 나타내며 인덱스 1을 보기 시작하지만 이미 전체 문자열을 알고 있기 때문입니다. 첫 번째 매칭 라운드 처음 4개의 문자가 매칭에 등장하지만 여전히 하나씩 반복해서 매칭해야 합니다. #🎜🎜##🎜🎜##🎜🎜#부분 일치 테이블/부분 일치 테이블#🎜🎜##🎜🎜##🎜🎜# 길이가 8인 abababca 문자열을 다음과 같이 가져옵니다. 예, 부분 일치 테이블은 다음과 같습니다. #🎜🎜#<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> 로그인 후 복사 로그인 후 복사 로그인 후 복사 값 행은 부분 일치 테이블의 값입니다. #🎜🎜##🎜🎜#Subset#🎜🎜##🎜🎜#위의 예시 문자열에서index가 2인 위치를 관찰하면 aba 문자열의 하위 집합이 얻어집니다. index가 7인 위치를 관찰하면 전체 문자열이 얻어지는 것이 분명합니다. 우리가 관찰하는 위치가 다르다는 것은 하위 문자열이 변경되었기 때문에 우리가 초점을 맞추고 있는 문자열의 하위 집합이 다르다는 것을 의미합니다. #🎜🎜##🎜🎜#Prefix & Suffix#🎜🎜##🎜🎜#주어진 문자열의 끝에서 하나 이상의 문자를 제거하고 나머지 부분을 진정한 접두사라고 합니다. 문자열(적절한 접두사), 이하 접두사라고 합니다. 여기서 "참"은 "참·접두사"를 의미하지 않습니다. 수학에서 집합의 "진위 부분 집합"을 생각해보세요. 예를 들어banana의 접두사는 #🎜🎜#
바나나, 접미사는 #🎜🎜#입니다.
部分匹配值可以看到，所有前缀和后缀在数量上是对称的，那么我们可以从前缀中找出一个，与后缀进行匹配，先不关心做这个匹配的意义。以最开始的文本 假如我们观察
将前缀依次在后缀中去匹配，这里前后缀列表中能够匹配上的只有 再比如来观察
此时可观察出其匹配项为 再比如来观察
然后拿前缀中每个元素与后缀中的元素进行匹配，最后找出有两个匹配项，
我们取长的这个 所以现在再来看上面的部分匹配表，一是能理解其值是怎么来的，二是能理解其表示的意义，即，所有前缀与后缀的匹配项中长度最长的那一个的长度。 当我们继续，进行到 再继续就到字符串末尾了，即整个字符串 <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue , 央è½̆é>…é»', Tahoma, Arial, sans-serif">nana<h2></h2></span><span style=" 글꼴 모음:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, å¼®è½̅é>…é»', Tahoma, Arial, sans-serif">ana</span>na
<span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, å½®è½́ é≥…é»', Tahoma, Arial, sans-serif">a<blockquote></blockquote></span>
부분분匹配值可以看到，所有前缀和 >abababca 为例。 🎜假如我们观察index 为 2 的位置，此时子字符串为 aba，其前后缀分别为：🎜🎜🎜前缀：a ，ab🎜后缀：ba ，a🎜将前缀依次在后缀中去匹配，这里前后缀列表中能够匹配上的只有 a 这个子字符串，其长島为 1，所以将这个观测结果填入表中丰下来，开始看到的part分匹配表吻合了。🎜🎜再比如来观察 index 为 3 的位置,此时得到的子符串为 abab,此时的前后缀为：🎜🎜🎜前缀： a，ab，aba🎜后缀：bab，ab ，b🎜此时可观察流其匹配项为 ab ，长为 2，也与상면부분匹配表中的值吻合。🎜🎜再比如来观察 index 为 5 的位置，此时子字符串为 ababab，前后缀为：🎜🎜🎜前缀：a code>，<code>ab，aba，abab，ababa🎜后缀：babab，<code>abab，bab，ab，b🎜然后拿前缀中每个元素与后缀中的元素进行匹配，最后找流有两个匹配项，🎜🎜🎜<span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, å¼®è½̅é>…é»', Tahoma, Arial, sans-serif">ab🎜</span>🎜<span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, å¼®è½̅é>…é»', Tahoma, Arial, sans-serif">abab🎜</span> 🎜我们取长的这个 abab，其长島为 4。🎜🎜所以现在再来看上表，一是能理解其值是怎严的，two 是能理 解其表示 的 心义 ， 即 ， 所有前缀与后缀 的匹配项中长島最长 的那一个 长島 .🎜🎜当我们继续 进行到 index为 6 时，子字符串为 abababc，可以预见，前后缀中找不到匹配。因为所有前缀都不包含 c，而所有后缀都包含 c。所以此时分匹配值为 0。🎜🎜再继续就到字符串末尾了，即整个字符串 abababca。也可以预见，因为所有前缀都以 a code> 开始，并且所有后缀都以 <code>a 结尾，所以此时的分匹配值最少为 1。继续会发现，因为后side的后缀开始有 c 정말 좋아요 ，使得后缀city包含 ca，而前缀中能够包含 c 的只有 abababc ，而该长島 7 与同等长島的后缀 bababca 不匹配。至此就可以得出结论，匹配结果就是 1，没有更长的匹配了。🎜🎜🎜part分匹配表的使用🎜🎜 🎜利사용 상부면적 부분匹配值,我们는 进行字符串查找时，不必每次失败后只移动一位，而是可以移动多位，去掉一些冗余的匹配。这里有个公式如下：🎜🎜🎜 🎜partial_match_length 길이의 부분 일치가 발견되고 테이블[partial_match_length] ] > 1, 부분 일치_길이 - 테이블[부분 일치_길이 - 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
