python教程—来自两个以上字符串的最长公共子字符串- Python-Python实用宝典

python教程—来自两个以上字符串的最长公共子字符串- Python

我正在寻找一个Python库,用于从一组字符串中找到最长的公共子字符串。解决这个问题有两种方法:

我正在寻找一个Python来查找一组字符串中最长的公共子字符串。解决这个问题有两种方法:

  • 使用后缀树
  • 使用动态编程。

实现的方法并不重要。重要的是,它可以用于一组字符串(不仅仅是两个字符串)。

回答

这些配对函数将在任意字符串数组中找到最长的公共字符串:

    def long_substr(data): substr = '' if len(data) > 1 and len(data[0]) > 0: for i in range(len(data[0])): for j in range(len(data[0])-i+1): if j > len(substr) and is_substr(data[0][i:i+j], data): substr = data[0][i:i+j] return substr def is_substr(find, data): if len(data) < 1 and len(find) < 1: return False for i in range(len(data)): if find not in data[i]: return False return True print long_substr(['Oh, hello, my friend.', 'I prefer Jelly Belly beans.', 'When hell freezes over!'])

毫无疑问,这个算法还可以改进,而且我还没有接触过太多Python,所以也许它在语法上也可以更有效,但它应该可以完成这项工作。

编辑:内联第二个is_substr函数,如J.F. Sebastian所示。用法保持不变。注:算法不变。

    def long_substr(data): substr = '' if len(data) > 1 and len(data[0]) > 0: for i in range(len(data[0])): for j in range(len(data[0])-i+1): if j > len(substr) and all(data[0][i:i+j] in x for x in data): substr = data[0][i:i+j] return substr

希望这有助于

杰森。

​Python实用宝典 (pythondict.com)
不只是一个宝典
欢迎关注公众号:Python实用宝典

本文由 Python实用宝典 作者:Python实用宝典 发表,其版权均为 Python实用宝典 所有,文章内容系作者个人观点,不代表 Python实用宝典 对观点赞同或支持。如需转载,请注明文章来源。
1

发表评论