Shulou(Shulou.com)06/02 Report--

This article mainly introduces Python how to achieve KPM algorithm, the article is very detailed, has a certain reference value, interested friends must read it!

Knowledge points:

Let's start with prefixes and suffixes.

For example, there is a string: abab

At the subscript 3 (the prefix and suffix are 1 less than the length indicated by the subscript, where the subscript is 3, the length is 4)

The prefix is: a _

The suffix is: bperfine babab

First, to get the next [] array of KPM algorithm

Let's briefly talk about the principle. First of all, k, the subscript used to store the prefix, first initialize jroom0 (j is used to represent the subscript of the pattern string, and go all the way to compare each bit of the pattern string with the previous one. If it is equal, then record which position is the same as the previous position. Here, we mainly want to record the next position of the same position, that is, the different position, and start the comparison from the same position. It is backtracking to a different location, so here we need jroom1 when t [j] = = t [k] is established. In order to compare whether the next position is the same, k also needs + 1), the pattern string starts at 0, and the first position of khammer Musi 1 next [0] =-1 is assigned the default value-1.

The string here uses = "abab"

First cycle:

Determine whether k is equal to-1, and if so, both j and k are + 1

Next [1] = 0, that is, the backtracking position of the second position (subscript 1) is still 0, because the maximum length of the prefix must be less than the length of the current position.

The second cycle:

To judge t [j] = = t [k], t [1] = = t [0], t [1] = "b", t [0] = "a", it is not equal.

Perform else:

K=next [0] =-1

The third cycle:

Kaohsiung Musi 1

Both j and k + 1 ~ (1) j ~ (2) ~ (2) ~ () ~ (2) ~ () ~ (- 1) ~ (- 1) ~ (- 1) ~ (- 1) ~ (- 1) ~ (- 1) ~ (2) ~ (- 1) ~ (- 1) ~ (- 1) ~ (- 1) ~ (2) ~ (- 1) ~ (- 1) ~ (2) ~ (- 1) ~ (- 1) ~ (- 1) and (2) ~ (- 1) ~ (2) ~ (())

The fourth cycle:

K is not equal to-1. Judge t [2] = = t [0], t [2] = "a" = t [0] = "a".

Both j and k + 1 ~ (1) j ~ 3 ~ 1 ~ (1) ~ (1) ~ (1) ~ (1)

At this time, next= [- 1 aba 0], next [3] = 1 means that when a mismatch occurs at next [3], that is, when the subscript of the pattern string is 3, it is "b", indicating that all the previous aba matches the target string, so the string aba in front of the mismatch position of the pattern string must be equal to the first three values in front of the mismatch position of the target string, that is, aba, so at this point, you only need to trace back to the 1 position of the pattern string, that is, the b of the pattern string. The pattern string b is preceded by a, which satisfies the previous an of the target string.

The fifth cycle:

K is still not equal to-1, that is, compare the two numbers after the previous position and then compare them. To put it simply, compare each item with the first term, and if there is equality, compare whether the next term is equal to the second term.

The code is as follows:

Def GetNext (t, next): J, k = 0,-1 next [0] =-1 while j

< len(t) - 1: if k == -1 or t[j] == t[k]: # 如果k==-1 或者 开始位置和结尾位置有相同的元素 j, k = j + 1, k + 1 # j和k都加1,当前位匹配，则从下一个位置开始匹配，所以k+1；j再进行取下一位判断是否也是匹配，所以也要+1 next[j] = k # 当前位置要取k项 else:#如果不相等，再把k置-1，下一次循环再进行+1操作，j这个位置再存入0，表示无匹配项 k = next[k] return next二、KMP函数 原理和BF算法是一样的，唯独不同的是，当模式串与目标串不匹配的时候，不直接回溯模式串，而是根据模式串的next[]表，查询要回溯到的位置，直接回溯到模式串的指定位置，KMP算法的核心也就在这里，但是这种方法一般只对前缀和后缀存在相同元素时，有效果，也就是说相同部分是一样的就不再进行比较了，从相同元素的下一个位置开始比较，所以KMP算法最复杂的部分其实就是找next[]表，要找出模式串的每一个位置，是否有相同前缀，如果有则标注该相同位置，下次回溯就不用回溯到0这个位置，可以从不相同位置开始。 def KMP(s, t): next = [0] * len(t) next = GetNext(t, next) print(next) i, j = 0, 0 while i < len(s) and j < len(t): if j == -1 or s[i] == t[j]: i, j = i + 1, j + 1 else: j = next[j] if j >

= len (t): return I-len (t) else: return-1

Complete code:

Def GetNext (t, next): J, k = 0,-1 next [0] =-1 while j

< len(t) - 1: if k == -1 or t[j] == t[k]: # 如果k==-1 或者 开始位置和结尾位置有相同的元素 j, k = j + 1, k + 1 # j和k都加1,当前位匹配，则从下一个位置开始匹配，所以k+1；j再进行取下一位判断是否也是匹配，所以也要+1 next[j] = k # 当前位置要取k项 else:#如果不相等，再把k置-1，下一次循环再进行+1操作，j这个位置再存入0，表示无匹配项 k = next[k] return next def KMP(s, t): next = [0] * len(t) next = GetNext(t, next) print(next) i, j = 0, 0 while i < len(s) and j < len(t): if j == -1 or s[i] == t[j]: i, j = i + 1, j + 1 else: j = next[j] if j >

= len (t): return I-len (t) else: return-1 if _ _ name__ = ='_ main__': re = KMP ('asdfghjsssaaasdfaaaabababcdabd', "ababaaaababaa") print (re)

Results:

These are all the contents of the article "how to implement the KPM algorithm in Python". Thank you for reading! Hope to share the content to help you, more related knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.