Python-最长的公共子字符串?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (175)

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

  • 使用suffix trees
  • 使用动态编程。

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

提问于
用户回答回答于

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

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!'])
用户回答回答于

我更喜欢这个is_substr,因为我觉得它更具可读性和直观性:

def is_substr(find, data):
  """
  inputs a substring to find, returns True only 
  if found for each data in data list
  """

  if len(find) < 1 or len(data) < 1:
    return False # expected input DNE

  is_found = True # and-ing to False anywhere in data will return False
  for i in data:
    print "Looking for substring %s in %s..." % (find, i)
    is_found = is_found and find in i
  return is_found

扫码关注云+社区

领取腾讯云代金券