Python最长公共子串算法实例

yipeiwu_com5年前Python基础

本文实例讲述了Python最长公共子串算法。分享给大家供大家参考。具体如下:

#!/usr/bin/env python 
# find an LCS (Longest Common Subsequence). 
# *public domain* 
 
def find_lcs_len(s1, s2): 
 m = [ [ 0 for x in s2 ] for y in s1 ] 
 for p1 in range(len(s1)): 
  for p2 in range(len(s2)): 
   if s1[p1] == s2[p2]: 
    if p1 == 0 or p2 == 0: 
     m[p1][p2] = 1
    else: 
     m[p1][p2] = m[p1-1][p2-1]+1
   elif m[p1-1][p2] < m[p1][p2-1]: 
    m[p1][p2] = m[p1][p2-1] 
   else:               # m[p1][p2-1] < m[p1-1][p2] 
    m[p1][p2] = m[p1-1][p2] 
 return m[-1][-1] 
 
def find_lcs(s1, s2): 
 # length table: every element is set to zero. 
 m = [ [ 0 for x in s2 ] for y in s1 ] 
 # direction table: 1st bit for p1, 2nd bit for p2. 
 d = [ [ None for x in s2 ] for y in s1 ] 
 # we don't have to care about the boundery check. 
 # a negative index always gives an intact zero. 
 for p1 in range(len(s1)): 
  for p2 in range(len(s2)): 
   if s1[p1] == s2[p2]: 
    if p1 == 0 or p2 == 0: 
     m[p1][p2] = 1
    else: 
     m[p1][p2] = m[p1-1][p2-1]+1
    d[p1][p2] = 3          # 11: decr. p1 and p2 
   elif m[p1-1][p2] < m[p1][p2-1]: 
    m[p1][p2] = m[p1][p2-1] 
    d[p1][p2] = 2          # 10: decr. p2 only 
   else:               # m[p1][p2-1] < m[p1-1][p2] 
    m[p1][p2] = m[p1-1][p2] 
    d[p1][p2] = 1          # 01: decr. p1 only 
 (p1, p2) = (len(s1)-1, len(s2)-1) 
 # now we traverse the table in reverse order. 
 s = [] 
 while 1: 
  print p1,p2 
  c = d[p1][p2] 
  if c == 3: s.append(s1[p1]) 
  if not ((p1 or p2) and m[p1][p2]): break
  if c & 2: p2 -= 1
  if c & 1: p1 -= 1
 s.reverse() 
 return ''.join(s) 
 
if __name__ == '__main__': 
 print find_lcs('abcoisjf','axbaoeijf') 
 print find_lcs_len('abcoisjf','axbaoeijf')

希望本文所述对大家的Python程序设计有所帮助。

相关文章

python利用拉链法实现字典方法示例

python利用拉链法实现字典方法示例

前言 字典也叫散列表,最大的特点是通过key来查找其对应的值其时间复杂度是O(1),下面这篇文章就来给大家介绍介绍python利用拉链法实现字典的方法。 在Python中怎样用列表实现字...

Python之列表实现栈的工作功能

问题: python中使用列表实现栈的功能 """ 栈的工作原理 入栈 出栈 查看栈顶元素 栈的长度 栈是否为空 """ stack = [] info = ""...

用python写一个定时提醒程序的实现代码

用python写一个定时提醒程序的实现代码

身体是革命的本钱,身体健康了我们才有更多精力做自己想做的事情,追求女神,追求梦想。然而程序员是一个苦比的职业,大部分时间都对着电脑,我现在颈椎就不好了,有时候眼睛还疼,我还没20阿,伤心...

OpenCV实现人脸识别

主要有以下步骤: 1、人脸检测 2、人脸预处理 3、从收集的人脸训练机器学习算法 4、人脸识别 5、收尾工作 人脸检测算法: 基于Haar的脸部检测器的基本思想是,对于面部正面大部分区域...

Python提取转移文件夹内所有.jpg文件并查看每一帧的方法

python里面可以将路径里面的\替换成/避免转义。 os.walk方法可以将目标路径下文件的root,dirs,files提取出来。后面对每个文件进行操作。 切片操作[:]判断是否为....