您的位置：首页 > 脚本大全 > > 正文

python字符串相似度匹配（Python实现字符串匹配的KMP算法）

更多 时间：2021-10-26 11:22:36 类别：脚本大全 浏览量：352

python字符串相似度匹配

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

kmp算法

kmp算法是一种改进的字符串匹配算法，由d.e.knuth，j.h.morris和v.r.pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称kmp算法）。kmp算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。

  • ?
  • 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
    		•
  • #! /usr/bin/python
  • # coding=utf-8
  • """
  • 基于这篇文章的python实现
  • http://blog.sae.sina.com.cn/archives/307
  • """
  • import unittest
  • def 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 0
  • def 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 false
  • class 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()
    		•

    总结

    以上所述是小编给大家介绍的python实现字符串匹配的kmp算法，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对开心学习网网站的支持！

    原文链接：https://www.cnblogs.com/goodspeed/p/3295456.html

    标签：Python 字符串 KMP
  • 上一篇：数据库常见的索引结构（数据库索引知识点整理）
  • 下一篇：mysql主键什么情况用uuid（Mysql主键UUID和自增主键的区别及优劣分析）
    • 您可能感兴趣
    首页 编程学习 Web前端 数据库 软件设计
    开心学习 ©2013-2021 保留所有权利