现在来写字符串匹配这种东西也许并非一件明智之事,抱着或许有人要看呢这种心态是完全没有必要的,而之所以以此为一个主题,也是当初自己作为小白被此折磨过许久,所以写这些内容权当回忆,与技术的关系反而不大了。

Brute

记得最开始学编程的时候就是用c写字符串匹配,那时候也就能想到brute的算法了, 相信没有人会不懂吧。

1
2
3
4
5
6
7
8
9
10
11
12
def brute(s,p):
    i = 0
    while i <= len(s)-len(p):
        j = 0
        while j < len(p):
            if s[i+j] != p[j]:
                break
            j += 1
        if j == len(p):
            return i
        i += 1
    return -1

KMP

后来其实很长一段时间都没有很关注这些东西了,主要是在学校上课考试等等brute就 已经足够了,知道KMP也是在网上无聊逛论坛的时候看到的,机缘巧合吧。

brute算法最明显的特点就是当发生一个不匹配的字符时,直接将回溯,从s串的下一个 重新开始匹配

s : a b c a b d a c a b c a b a b f

p : a b c a b a

p : _ a b c a b a

p : _ _ _ a b c a b a

(以下论述中的数组概念以python中数组为准)

可以看出当p[5](a)和s[5](d)出现不匹配情况的时候,brute算法是直接将p右移一个字符,而实际情况是,当p[5](a)出现不匹配情况时,p[0:5](abcab)都是匹配的,那么此时p应该右移多少呢?我们大概的看下,就可以看出来应该右移3位,即用p[2]s[5]比较,因为既然abcab匹配,那么s[5]前面一定是ab,刚好可以和p的前两位匹配,所以我们就可以从p[2]与s[5]的比较开始匹配。

上面的推断是通过对abcab观察得来的,那么具体的规律又是什么呢?首先介绍前缀后缀的概念:

字符串的前缀就是指以字符串首字符开始的子字符串,例如h,he都是hello的前缀,后缀也是如此,以字符串尾字符结尾的子字符串,o,lo,llo都是hello的后缀。

那么我们看刚才我们对abcab的处理,我们是看到p[0:2] == p[3:5]来得出当p[5]不匹配时可以立刻尝试用p[2]来匹配,也就是当p[i]和s[j]不匹配时,我们就观察q = p[0:i],找到q的前缀等于后缀中最长的一个p[0:k],在abcab中就是ab了,然后我们就知道这个前缀就不用匹配了,所以我们就可以马上比较p[k]s[j]。那么我们怎么证明这种移动方法就是对的呢?

反证法,如果可以少移动,那么就是p[k+r]s[j]比较,而p[0:k+r] == p[i-k-r,i],那么p[0:i]中前缀等于后缀中最长的就不是p[0:k]了,命题得证!由此可见那么最长的条件是必不可少的。

那么现在问题就是对应每个i,我们如何求出k?

为了下文方便,首先我们定义数组next满足next[i] = k

我们可以分析下满足性质Q(q的前缀等于q的后缀中最长的一个)的k的特点:

如果已知next[i] = k,那么p[0:k] == p[i-k:i],

  • 那么如果p[i] == p[k],则next[i+1] = k+1;

  • 如果p[i] != p[k],那么我们如何来找最长前缀呢?我们现在唯一知道的就是p[0:k] == p[i-k:i],此时用p[k]比较肯定不行了,那么我们找谁呢?p[k-1]还等于谁呢?想到这,思路就有了,如果知道next[k] = t,就一定有p[0:t] == p[k-t,k],即p[k-1] == p[t-1],此时如果p[i] == p[t],则p[i+1] = p[t]+1, 否则就再找next[t]……

那么递归到什么时候停止呢,如果 k==0 那么就不存在p[0:0]了,这个时候我们知道当p[i]s[j]不匹配时,直接比较p[0]和s[j]就行了,即next[i] = 0,那么我们就开始写代码吧。

首先我们需要明确起始值, next[0] = -1p[0]s[j]不匹配时,s[j]不需要再比较了,p右移一位,相当于s[j]与p[-1]比较。

那个具体的代码就和上面的分析类似:

1
2
3
4
5
6
7
8
9
10
11
12
13
def genNext(pattern):
    length = len(pattern)
    next = [0] * (length+1)
    next[0] = -1
    j,k = 0, -1
    while j < length:
        if k == -1 or pattern[j] == pattern[k]:
            j += 1
            k += 1
            next[j] = k
        else:
            k = next[k]
    return next[:length]

具体的匹配匹配过程:

1
2
3
4
5
6
7
8
9
10
11
12
def kmp(s,p):
    next = genNext(p)
    i,j = 0,0
    while i < len(s):
        if j == -1 or s[i] == p[j]:
            i += 1
            j += 1
        else:
            j = next[j]
        if j == len(p):
            return i-j
    return -1

img