输出最长公共子序列 - 来自两个以上字符串的最长公共子字符串-Python




求公共子串 (5)

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

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

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

https://code.i-harness.com


如果有人正在寻找一个通用版本,它也可以获取任意对象序列的列表:

def get_longest_common_subseq(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_subseq_of_any(data[0][i:i+j], data):
                    substr = data[0][i:i+j]
    return substr

def is_subseq_of_any(find, data):
    if len(data) < 1 and len(find) < 1:
        return False
    for i in range(len(data)):
        if not is_subseq(find, data[i]):
            return False
    return True

# Will also return True if possible_subseq == seq.
def is_subseq(possible_subseq, seq):
    if len(possible_subseq) > len(seq):
        return False
    def get_length_n_slices(n):
        for i in xrange(len(seq) + 1 - n):
            yield seq[i:i+n]
    for slyce in get_length_n_slices(len(possible_subseq)):
        if slyce == possible_subseq:
            return True
    return False

print get_longest_common_subseq([[1, 2, 3, 4, 5], [2, 3, 4, 5, 6]])

print get_longest_common_subseq(['Oh, hello, my friend.',
                                     'I prefer Jelly Belly beans.',
                                     'When hell freezes over!'])

您可以使用SuffixTree模块,该模块是基于广义后缀树的ANSI C实现的包装器。 该模块易于操作....

看看: here


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

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函数,如JF 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

希望这可以帮助,

杰森。


这可以缩短:

def long_substr(data):
  substrs = lambda x: {x[i:i+j] for i in range(len(x)) for j in range(len(x) - i + 1)}
  s = substrs(data[0])
  for val in data[1:]:
    s.intersection_update(substrs(val))
  return max(s, key=len)

set(可能)实现为哈希映射,这使得效率有点低。 如果你(1)实现一个set数据类型作为trie和(2)只是将后缀存储在trie中然后强制每个节点成为一个端点(这相当于添加所有子串),那么理论上我会猜测这个宝宝的记忆效率很高,特别是因为尝试的交叉点非常容易。

然而,这是短暂的,过早的优化是大量浪费时间的根源。


def common_prefix(strings):
    """ Find the longest string that is a prefix of all the strings.
    """
    if not strings:
        return ''
    prefix = strings[0]
    for s in strings:
        if len(s) < len(prefix):
            prefix = prefix[:len(s)]
        if not prefix:
            return ''
        for i in range(len(prefix)):
            if prefix[i] != s[i]:
                prefix = prefix[:i]
                break
    return prefix

来自http://bitbucket.org/ned/cog/src/tip/cogapp/whiteutils.py







longest-substring