字符串匹配粗探讨

最近耽于iGEM，总想搞点独特的算法，需要用到字符串匹配，写个笔记在这里。

$$P_k$$表示P的前k个字符的字串。

自动机：

神奇而优美的东西

KMP：

首先问这样一个问题：

想在T中找到一个串和P相等。那么我们已知扫描了到了这样一个结果

$$P[1..q]==T[s..s+q]$$

那么下一个s’满足

$$P[1..k]==T[s’..s’+k]$$的s’是什么。

如果知道了这个问题的答案，我们可以轻松在s和下一个s’内跳跃（多么象自动机），从而在超级短的时间内完成查找。

再回头看这个问题，其实找到这个$$s’$$已经和T没有任何的关系。这仅仅是P自身的性质。

于是，我们拿P与自身比较，做一个预处理，很容易得到这个s和s’的关系。

回到我们的问题，我们实际上处理了这样一个事情：

找到$$P_k$$使得$$P_k$$为$$P_q$$的最长后缀。

于是我们定义前缀函数为

$$\pi[k]=max(k,P_k为P_q的最长后缀$$

然后预处理So easy,

1. def makepi(P):
2.     pi=[0]*len(P)
3.     for i in range(len(P)):
4.         for j in range(i,-1,-1):
5.             if(houzhui(P[0:j],P[0:i+1])):
6.                 pi[i]=j
7.                 break
8.     return pi

于是，我们就有了一个强力的算法，

1. 置i为0，开始做KMP
2. 找到i以后T,P的最长匹配。如果长度l和P相等，则输出结果
3. 由前缀函数找到位移量$$(i+=l+i-\pi[i])$$，若位移量为0则自加.重复2
4. 直到刷完。

其实结合前面自动机的做法，KMP不如说是自动机针对字符串匹配这一单一问题的神级优化.

写为代码，上面的玩意大概是这么回事

1. def KMP_Difficult(T,P):
2.     pi=makepi(P)
3.     print pi
4.     i=0
5.     while i<len(T):
6.         print i
7.         for j in range(len(P)):
8.             if(i+j>=len(T)):
9.                 return
10.             if(P[j]!=T[i+j]):
11.                 break
12.             if(j==len(P)-1):
13.                 print “res”,i
14.         i=i+max(j–pi[j],1)

奇怪，是一种$$O(nm)$$的算法，这并不是我们想要的。

仔细观察，发现问题出现在j的循环上，这个过程中我们做了很多重复性的工作，因为我们的定义包含了这样一个信息

由现在的下标s和匹配数可以直接得到最近的s’使得s’是s..s’内匹配的最好的一个结果

我们关心的完全可以不是从某点开始的最多匹配长度，而是到这个点迄今为止的最大匹配数量。那么我们算法可以改为

i从1到n循环

定义q为到i为止最长匹配数量。

于是P[q]==T[i]那么q可以自加一个了。

P[q]!=T[i]，那就用我们的前缀函数寻找现在的q=$$\pi[q]$$

q=len(P)匹配正确。

于是呢，我们这么写了代码

1. def KMP(T,P):
2.     pi=makepi(P)
3.     q=0
4.     print pi
5.     for i in range(len(T)):
6.         if(T[i]==P[q]):
7.             q+=1
8.             if(q==len(P)):
9.                 print “res”,i–q+2
10.                 q=pi[q–1]
11.         else:
12.             q=pi[q]

All Done!

That’s Cool!