Python实现字符串匹配的KMP算法

#! /usr/bin/python# coding=utf-8"""基于这篇文章的python实现http://blog.sae.sina.com.cn/archives/307"""import unittestdef pmt(s):  """  PartialMatchTable  """  prefix = [s[:i+1] for i in range(len(s)-1)]  postfix = [s[i+1:] for i in range(len(s)-1)]  intersection = list(set(prefix) & set(postfix))  if intersection:    return len(intersection[0])  return 0def kmp(big,small):  i = 0  while i < len(big) - len(small) + 1:    match = True    for j in range(len(small)):      if big[i+j] != small[j]:         match = False        break    if match:      return True    #移动位数 = 已匹配的字符数  对应的部分匹配值    if j:      i += j - pmt(small[:j])    else:      i += 1  return Falseclass kmpTests(unittest.TestCase):  def test_pmt(self):    self.assertEqual(pmt("A"),0)    self.assertEqual(pmt("AB"),0)    self.assertEqual(pmt("ABC"),0)    self.assertEqual(pmt("ABCD"),0)    self.assertEqual(pmt("ABCDA"),1)    self.assertEqual(pmt("ABCDAB"),2)    self.assertEqual(pmt("ABCDABD"),0)    self.assertEqual(pmt("AAAAAA"),5)  def test_kmp(self):    self.assertTrue(kmp("ABCD","CD"))    self.assertFalse(kmp("ABCD","BD"))    self.assertTrue(kmp("BBC ABCDAB ABCDABCDABDE","ABCDABD"))if __name__ == '__main__':  unittest.main()