elegant python

First, let’s take a look at the simple matching of strings.

can be imagined as fixing the text string s, and aligning the pattern string p starting from the leftmost side of s. If the aligned parts are exactly the same, the match is successful. If it fails, the pattern will be Move the entire string p to the right by 1 bit, continue to check the alignment part, and repeat.

#Naive match
def naive_match(s, p):
m = len(s); n = len(p)
for i in range(m-n+1):#Start pointer i
if s[i:i+n] == p:
Yifeng's . After reading it all the way, it suddenly became clear.
In fact, it is to preprocess the pattern string p to obtain a partial matching table of suffixes and suffixes, so that we can use known information to calculate How many bits to shift right. That is, kmp = naive matching + moving multiple bits.
For more details, please see Ruan Yifeng’s article, which will not be discussed here.
The python code implementation is given below.

#KMP
def kmp_match(s, p):

m = len(s); n = len(p)

cur = 0#Start pointer cur
table = partial_table(p)
while cur<=m-n:
for i in range(n):
if s[i+cur]!=p[i]:
cur += max(i - table[i-1], 1)# With the partial matching table, we are not just Shift 1 bit to the right, you can move multiple bits at a time
            break
        else:
                                  ’ ’ ’ ’ ’ ’ ’ ''part ’s ’s ’ ’ ’ ’’’’ through through out out off right out out off out out out out out out out out out out spent so so so so so so so so so so so so so so so so so so so so so so so so so so so so to so so so so so so so so so so so so so so so so so so to so so so so so so so so so so so to so so so so so so so so to so... DABD") -> ; [0, 0, 0, 0, 1, 2, 0]'''
prefix = set()
postfix = set()
ret = [0]
for i in range(1,len(p)) :
prefix.add(p[:i])
postfix = {p[j:i+1] for j in range(1,i+1)}
ret.append(len((prefix&postfix or {''} ).pop()))
return ret

print naive_match("BBC ABCDAB ABCDABCDABDE", "ABCDABD")
print partial_table("ABCDABD")
print kmp_match("BBC ABCDAB ABCDABCDABDE", "ABCDABD")



The above is the content of elegant python. For more related content, please pay attention to the PHP Chinese website (www.php.cn)!