字符串匹配粗探讨

最近耽于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_kP_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!

发表评论

电子邮件地址不会被公开。 必填项已用*标注