前端之家收集整理的这篇文章主要介绍了
Python 寻找最长公共子串的简单示例,
前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
感兴趣Python 寻找最长公共子串的简单示例的小伙伴,下面一起跟随编程之家 jb51.cc的小编来看看吧。<br>
# 编程之家 (jb51.cc)
def find_lcp(s,t):
lens = len(s)
lent = len(t)
if not lens or not lent:
return 0
longest = 0
for i in range(lens):
for j in range(lent):
length = 0
m = i
n = j
while m < lens and n < lent:
if s[m] != t[n]:
break
length += 1 #相等则两个字符串均向后移动一位
m += 1
n += 1
if longest < length:
sub =''
sub += s[m-length:m] #或者sub += t[n-length:n]
longest = length
return longest,sub
if __name__ == '__main__':
print(find_lcp('abcdefg','aabcabcd')) #(4,'abcd')
# End 512.笔记 jb51.cc
上述的
实现方法对s和t串进行逐个字符比较,其中循环有三层,复杂度为o(n^3),《大话数据结构》里有一个逐步改进的KMP算法,以后再补充吧