#!/user/bin/env python
# -*- coding: utf-8 -*-
class arithmetic():
def __init__(self):
pass
''' 【编辑距离算法】 【levenshtein distance】 【字符串相似度算法】 '''
def levenshtein(self,first,second):
if len(first) > len(second):
first,second = second,first
if len(first) == 0:
return len(second)
if len(second) == 0:
return len(first)
first_length = len(first) + 1
second_length = len(second) + 1
distance_matrix = [range(second_length) for x in range(first_length)]
#print distance_matrix
for i in range(1,first_length):
for j in range(1,second_length):
deletion = distance_matrix[i-1][j] + 1
insertion = distance_matrix[i][j-1] + 1
substitution = distance_matrix[i-1][j-1]
if first[i-1] != second[j-1]:
substitution += 1
distance_matrix[i][j] = min(insertion,deletion,substitution)
#print distance_matrix
return distance_matrix[first_length-1][second_length-1]
def lcs(self,first,second):
first_length = len(first)
second_length = len(second)
size = 0
x = 0
y = 0
matrix = [range(second_length) for x in range(first_length)]
#print matrix
for i in range(first_length):
for j in range(second_length):
#print i,j
if first[i] == second[j]:
if i - 1 >= 0 and j - 1 >=0:
matrix[i][j] = matrix[i-1][j-1] + 1
else:
matrix[i][j] = 1
if matrix[i][j] > size:
size = matrix[i][j]
x = j
y = i
else:
matrix[i][j] = 0
#print matrix
#print size,x,y
return second[x-size+1:x+1]
if __name__ == "__main__":
arith = arithmetic()
print arith.levenshtein('GUMBOsdafsadfdsafsafsadfasfadsfasdfasdfs','GAMBOL00000000000dfasfasfdafsafasfasdfdsa')
print arith.lcs('GUMBOsdafsadfdsafsafsadfasfadsfasdfasdfs','GAMBOL00000000000dfasfasfdafsafasfasdfdsa')
from:http://www.lamprisi.com/forum.php?mod=viewthread&tid=3935&highlight=LCS
分享到:
相关推荐
实现了求最长公共子序列的算法,内容简单易懂,代码也很短
比较两个字符串的相似度,利用LCS算法计算出两个字符串的最长公序列,根据最长公序列得出相似度,例如: 字符串1:1234 字符串2:51234,则他们的相似度为:4*2/(4+5)。
最长公共子序列的算法实现,采用递归方法。
根据LCS算法取出最长公用字符串,实现字符串比较
最长公共字串算法,为算法导论上的算法,可以运行,运行时间为O(mn)
最长公共子序列算法LCS实现。任意输入两个字符串,通过此算法可以找到最长的公共子序列。
LCS最长公共子序列,完全正确的C++代码!
题目:如果字符串一的所有字符按其在字符串...分析:求最长公共子序列(Longest Common Subsequence, LCS)是一道非常经典的动态规划题,因此一些重视算法的公司像MicroStrategy都把它当作面试题。 完整介绍动态规划将
在 O(n log n) 时间空间预处理后(或较复杂的 O(n) 时间空间 预处理), 可以 O(1) 回答: 两个子串的最长公共前缀 (LCP)、最 长公共后缀 (LCS)。 对于拥有周期 p 的串 s, LCP(s[1..n], s[1 + p..n]) = n − p。 输入 ...
关于LCS(最长公共子序列)算法的实现~ 自己测试通过的
采用动态规划法与回溯法实现了lcs算法,并显示各算法运行时间,便于对不同的输入数据测试这两个算法的优劣。
主要内容 需要掌握的内容 字符串循环左移 LCS最长递增子序列 字符串全排列 递归、非递归 KMP Huffman编码 需要了解的内容 Manacher算法 BM算法 数据结构-字符串全文共87页,当前为第3页。 字符串循环左移 4/88 给定...
最长公共子序列(LCS)算法实验 最长公共子序列(LCS)算法实验 最长公共子序列(LCS)算法实验
最长子序列LCS算法,用于处理最长公共字串问题。 两个序列的LCS问题包含两个序列的前缀的LCS,因此,LCS问题具有最优子结构性质。在设计递归算法时,不难看出递归算法具有子问题重叠的性质。 设C[i,j]C[i,j]...
LCS算法的简单java实现,可以一起讨论学习
最长公共子序列,动态规划算法可有效地解此问题。下面我们按照动态规划算法设计的各个步骤来设计一个解此问题的有效算法
动态规划:最长公共子串 LCS 动态规划:最长公共子串 LCS
运用动态规划算法解决最长公共子序列问题,计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=, x2, …, xm>和Y=, y2, …, yn>作为输入。输出两个数组c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存储Xi与...
给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence)。比如字符串1:BDCABA;字符串2:ABCBDAB。则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA 二、算法求解 这是一个...