发布于 

字符串匹配笔记 | 笔记整理!

字符串匹配笔记 | 笔记整理!

字符串匹配问题总结

前置信息 | 初始化 | 传入信息

1
2
3
4
5
6
7
8
9
def __init__(self,strs,target) -> None:
    self.s=strs
    self.t=target

    self.m=len(self.s)
    self.n=len(self.t)

    self.nxt=[0]*(self.n+1)
    self.nxtval=[0]*(self.n+1)

朴素匹配 | 逐个对比

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def plain_match(self):
    ans=-1
    for i in range(self.m-self.n+1):
        k=i
        flag=1
        for j in range(self.n):
            if self.s[k]!=self.t[j]:
                flag=0
                break
            else:
                k+=1
        if flag:
            ans=i
            break
    return ans

字符串哈希 | 存在理论上失败的可能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class BKDRHash():
    def __init__(self,strs,target) -> None:
        self.s=strs
        self.t=target

        self.m=len(self.s)
        self.n=len(self.t)

        self.pp=131
        self.pre=[0]*self.m
        self.pattern_val=-1

        self.ans=-1
    # 求取匹配串的哈希数值
    def get_v(self):
        for k,v in enumerate(self.t):
            cur=ord(v)-ord('a')+1
            if k:
                self.pattern_val=self.pattern_val*self.pp+cur
            else:
                self.pattern_val=cur
    # 利用前缀哈希和 求取
    def get_ans(self):
        for k,v in enumerate(self.s):
            cur=ord(v)-ord('a')+1
            if k:
                self.pre[k]=self.pre[k-1]*self.pp+cur
            else:
                self.pre[k]=cur

            if k==self.n-1:
                if self.pre[k]==self.pattern_val:
                    self.ans=0
                    break
            if k>self.n-1:
                val=self.pre[k]-self.pre[k-self.n]*pow(self.pp,self.n)
                if self.pattern_val==val:
                    self.ans=k+1-self.n
                    break
    def run(self):
        self.get_v()
        self.get_ans()
        return self.ans

kmp算法 | 求next nextval数组逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def get_next(self):
    j=0
    for i in range(1,self.n):
        while j and self.t[i]!=self.t[j]:
            j=self.nxt[j]
        if self.t[i]==self.t[j]:
            j+=1
        self.nxt[i+1]=j

def get_nextval(self):
    j=0
    for i in range(1,self.n):
        while j and self.t[i]!=self.t[j]:
            j=self.nxtval[j]
        if self.t[i]==self.t[j]:
            j+=1
        self.nxtval[i+1]=j
        
        # 纯直接丑陋思路 | 没想到更好的 不过这样也不错!
        if self.t[self.nxtval[i]]==self.t[i]:
            self.nxtval[i]=self.nxtval[self.nxtval[i]]

def get_key(self,nxt):
    ans=-1
    j=0
    for i in range(self.m):
        while j and self.s[i]!=self.t[j]:
            j=nxt[j]
        if self.s[i]==self.t[j]:
            j+=1
        if j==self.n:
            ans=i+1-self.n
            break
    return ans

def get_key_bool(self,nxt):
    return self.get_key(nxt)!=-1

拓展kmp(Z)算法 | 不同写法

0-base

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 拓展kmp算法! |
def extend_kmp_1_base(self,s):
    l,r=1,0
    s='0'+s
    n=len(s)
    z=[0]*(n)
    for i in range(2,n):
        if i>r:
            z[i]=0
        else:
            k=i-l+1
            z[i]=min(z[k],r-i+1)
        while i+z[i]<n and s[i+z[i]]==s[1+z[i]]:
            z[i]+=1
        if i+z[i]-1>r:
            l,r=i,i+z[i]-1
    return z

1-Base

1
2
3
4
5
6
7
8
9
10
11
12
13
def extend_kmp_0_base(self,s):
    l,r=0,-1
    n=len(s)
    z=[0]*n
    for i in range(1,n):
        if i<=r:
            k=i-l+1
            z[i]=min(z[k],r-i+1)
        while i+z[i]<n and s[i+z[i]]==s[0+z[i]]:
            z[i]+=1
        if i+z[i]-1>r:
            l,r=i,i+z[i]-1
    return z

完整代码 | 哈希字符串 + Kmp

哈希字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Kmp():
    def __init__(self,strs,target) -> None:
        self.s=strs
        self.t=target

        self.m=len(self.s)
        self.n=len(self.t)

        self.pp=131
        self.pre=[0]*self.m
        self.pattern_val=-1

        self.ans=-1
    # 求取匹配串的哈希数值
    def get_v(self):
        for k,v in enumerate(self.t):
            cur=ord(v)-ord('a')+1
            if k:
                self.pattern_val=self.pattern_val*self.pp+cur
            else:
                self.pattern_val=cur
    # 利用前缀哈希和 求取
    def get_ans(self):
        for k,v in enumerate(self.s):
            cur=ord(v)-ord('a')+1
            if k:
                self.pre[k]=self.pre[k-1]*self.pp+cur
            else:
                self.pre[k]=cur

            if k==self.n-1:
                if self.pre[k]==self.pattern_val:
                    self.ans=0
                    break
            if k>self.n-1:
                val=self.pre[k]-self.pre[k-self.n]*pow(self.pp,self.n)
                if self.pattern_val==val:
                    self.ans=k+1-self.n
                    break
    def run(self):
        self.get_v()
        return self.get_ans()

Kmp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
class Kmp():
    def __init__(self,strs,target) -> None:
        self.s=strs
        self.t=target

        self.m=len(self.s)
        self.n=len(self.t)

        self.nxt=[0]*(self.n+1)
        self.nxtval=[0]*(self.n+1)
    def plain_match(self):
        ans=-1
        for i in range(self.m-self.n+1):
            k=i
            flag=1
            for j in range(self.n):
                if self.s[k]!=self.t[j]:
                    flag=0
                    break
                else:
                    k+=1
            if flag:
                ans=i
                break
        return ans
            
    def get_next(self):
        j=0
        for i in range(1,self.n):
            while j and self.t[i]!=self.t[j]:
                j=self.nxt[j]
            if self.t[i]==self.t[j]:
                j+=1
            self.nxt[i+1]=j
    
    def get_nextval(self):
        j=0
        for i in range(1,self.n):
            while j and self.t[i]!=self.t[j]:
                j=self.nxtval[j]
            if self.t[i]==self.t[j]:
                j+=1
            self.nxtval[i+1]=j
            
            # 纯直接丑陋思路 | 没想到更好的 不过这样也不错!
            if self.t[self.nxtval[i]]==self.t[i]:
                self.nxtval[i]=self.nxtval[self.nxtval[i]]
    
    def get_key(self,nxt):
        ans=-1
        j=0
        for i in range(self.m):
            while j and self.s[i]!=self.t[j]:
                j=nxt[j]
            if self.s[i]==self.t[j]:
                j+=1
            if j==self.n:
                ans=i+1-self.n
                break
        return ans

    def get_key_count(self,nxt):
        ans=j=0
        for i in range(self.m):
            while j and self.s[i]!=self.t[j]:
                j=nxt[j]
            if self.s[i]==self.t[j]:
                j+=1
            if j==self.n:
                j=nxt[j]
                ans+=1
        return ans

    def get_key_bool(self,nxt):
        return self.get_key(nxt)!=-1

    # 拓展kmp算法! |
    def extend_kmp_1_base(self,s):
        l,r=1,0
        s='0'+s
        n=len(s)
        z=[0]*(n)
        for i in range(2,n):
            if i>r:
                z[i]=0
            else:
                k=i-l+1
                z[i]=min(z[k],r-i+1)
            while i+z[i]<n and s[i+z[i]]==s[1+z[i]]:
                z[i]+=1
            if i+z[i]-1>r:
                l,r=i,i+z[i]-1
        return z
    def extend_kmp_0_base(self,s):
        l,r=0,-1
        n=len(s)
        z=[0]*n
        for i in range(1,n):
            if i<=r:
                k=i-l+1
                z[i]=min(z[k],r-i+1)
            while i+z[i]<n and s[i+z[i]]==s[0+z[i]]:
                z[i]+=1
            if i+z[i]-1>r:
                l,r=i,i+z[i]-1
        return z
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

快来参与讨论吧