KMP 알고리즘을 쉽게 이해할 수 있습니다.-JS 튜토리얼-php.cn

집

웹 프론트엔드

JS 튜토리얼

KMP 알고리즘을 쉽게 이해할 수 있습니다.

little bottle

Apr 30, 2019 pm 02:25 PM

jskmp연산

KMP(Knuth-Morris-Pratt 알고리즘) 알고리즘은 문자열 일치에 사용되어 문자열에서 특정 하위 문자열을 찾습니다. 하지만 이해하고 익히기가 쉽지 않습니다. 부분 매칭 테이블의 개념을 이해하는 것이 KMP 알고리즘을 이해하는 열쇠입니다.

여기서 논의는 모호한 논리를 피하고 적용을 통해 이해하는 데 중점을 둡니다.

String search

예를 들어 문자열 abcdef 하위 문자열에서 abcdg를 찾습니다. . abcdef 中找出 abcdg 子字符串。

朴素的解法，我们可以这样做，

分别取出第一位进行匹配，如果相同再取出各自的第二位。
如果不同，则将索引后移一位，从总字符串第二位开始，重复步骤一。

这种朴素解法的弊端在于，每次匹配失败，索引只后移一位，有很多冗余操作，效率不高。

在进行第一轮匹配中，即索引为 0 时，我们能够匹配出前四个字符 abcd 是相等的，后面发现想要的 g 与真实的 e 不符，标志着索引为 0 的情况匹配失败，开始查看索引为 1 时，但因为我们在第一轮匹配中，已经知道了总字符串中前四个字符的长相，但还是需要重复地挨个进行匹配。

部分匹配表/Partial Match Table

以长度为 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>

其中 value 行便是部分匹配表的值。

子集

对于上面示例字符串，假如我们观察第 index 为 2 的位置，那么我们得到了字符串的一个子集 aba，如果我们观察 index 为 7 的位置，那得到的是整个字符串，这点是很显然的。当我们观察的位置不同时，表示我们关注的字符串中的子集不同，因为子字符串发生了变化。

前缀 & 后缀

对于给定的字符串，从末尾开始去掉一个或多个字符，剩下的部分都叫作该字符串的真前缀（Proper prefix），后面简称前缀。这里「真」不是「真·前缀」的意思，联想一下数学里面集合的「真子集」。比如 banana，其前缀有：

b
ba
ban
bana
banan

同理，从首部开始，去掉一个或多个字条，剩下的部分是该字符串的真后缀（Proper suffix）。还是 banana

간단한 해결 방법은 다음과 같습니다. #🎜🎜#

첫 번째 숫자를 각각 빼서 일치시키고, 같으면 두 번째 숫자를 빼냅니다.
다른 경우 전체 문자열의 두 번째 위치부터 인덱스를 한 위치 뒤로 이동하고 1단계를 반복합니다.

#🎜🎜#이 간단한 솔루션의 단점은 일치가 실패할 때마다 인덱스가 한 위치 뒤로만 이동하므로 중복 작업이 많고 효율적이지 않다는 것입니다. #🎜🎜##🎜🎜#첫 번째 매칭 단계, 즉 인덱스가 0일 때 처음 네 문자 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의 접두사는 #🎜🎜#

b#🎜🎜#
…é»', Tahoma, Arial, sans-serif">ba #🎜 🎜#
ban#🎜🎜#
…é»', Tahoma, Arial, sans-serif">bana#🎜🎜# li>
…é»', Tahoma, Arial, sans-serif">banan#🎜🎜#

#🎜🎜#마찬가지로 헤더부터 시작하여 하나 이상의 단어를 제거하고 나머지 부분은 문자열입니다. 적절한 접미사. 또는 바나나, 접미사는 #🎜🎜#입니다.

…é»', Tahoma, Arial , sans-serif">anana<code style="white-space: nowrap;">anana
nana
ana
na
a

部分匹配值

可以看到，所有前缀和后缀在数量上是对称的，那么我们可以从前缀中找出一个，与后缀进行匹配，先不关心做这个匹配的意义。以最开始的文本 abababca 为例。

假如我们观察 index 为 2 的位置，此时子字符串为 aba，其前后缀分别为：

前缀：a，ab
后缀：ba，a

将前缀依次在后缀中去匹配，这里前后缀列表中能够匹配上的只有 a 这个子字符串，其长度为 1，所以将这个观测结果填入表中记下来，与开始看到的部分匹配表吻合了。

再比如来观察 index 为 3 的位置，此时得到的子字符串为 abab，此时的前后缀为：

前缀：a，ab，aba
后缀：bab，ab，b

此时可观察出其匹配项为 ab，长度为 2，也与上面部分匹配表中的值吻合。

再比如来观察 index 为 5 的位置，此时子字符串为 ababab，前后缀为：

前缀：a，ab，aba，abab，ababa
后缀：babab，abab，bab，ab，b

然后拿前缀中每个元素与后缀中的元素进行匹配，最后找出有两个匹配项，

ab
abab

我们取长的这个 abab，其长度为 4。

所以现在再来看上面的部分匹配表，一是能理解其值是怎么来的，二是能理解其表示的意义，即，所有前缀与后缀的匹配项中长度最长的那一个的长度。

当我们继续，进行到 index 为 6 时，子字符串为 abababc，可以预见，前后缀中找不到匹配。因为所有前缀都不包含 c，而所有后缀都包含 c。所以此时部分匹配值为 0。

再继续就到字符串末尾了，即整个字符串 abababca。也可以预见，因为所有前缀都以 a 开始，并且所有后缀都以 a 结尾，所以此时的部分匹配值最少为 1。继续会发现，因为后面的后缀开始有 c 的加入，使得后缀都包含 ca，而前缀中能够包含 c 的只有 abababc，而该长度 7 与同等长度的后缀 bababca

<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>

<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] 문자를 건너뛸 수 있습니다.🎜🎜

如果匹配过程中，匹配到了部分值为 partial_match_length，即目前找出前 partial_match_length 个字符是匹配的，将这个长度减一作为部分匹配表格中的 index 代入，查找其对应的 value 即 table[partial_match_length-1]，那么我们可以向前移动的步长为 partial_match_length - table[partial_match_length - 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>

假设需要从 bacbababaabcbab 中查找 abababca，根据上面的公式我们来走一遍。

首次匹配发生在总字符串的第二个字符，

<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，所以我们可以向前移动的距离是 1-0 1。其实也相当于没有跳跃，就是正常的本次匹配失败，索引后移一位的情况。这里没有节省任何成本。

继续直到再次发生匹配，此时匹配到的情况如下：

<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，查找到 table[partial_match_length-1] 即 index 为 2 对应的值为 1，所以可向前移动的距离为

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>

此时我们需要查找的字符串其长度已经超出剩余可用来匹配的字符串了，所以可直接结束匹配，得到结论：没有查找到结果。