查找长度 >= 4 的多个最长公共前导子串

Question

在 Python 中，我试图从列表中提取所有包含至少 4 个字符的最长公共前导子字符串。例如，在下面名为 "data" 的列表中，符合我的条件的 2 个最长公共子串是 "johnjack" 和 "detc"。我知道如何用下面的代码找到最长的公共子串，它没有返回任何内容（如预期的那样），因为没有公共子串。但是我正在努力构建一个可以检测列表中多个公共子字符串的脚本，其中每个公共子字符串的长度必须为 4 或以上。

data = ['johnjack1', 'johnjack2', 'detc22', 'detc32', 'chunganh']

def ls(data):
    if len(data)==0:
        prefix = ''
    else:
        prefix = data[0]
    for i in data:
        while not i.startswith(prefix) and len(prefix) > 0:
            prefix = prefix[:-1]
    print(prefix)

ls(data)

Answer 1

这是一个，但我认为它可能不是最快或最有效的。让我们从我们的答案的数据和容器开始：

data = ['johnjack1', 'johnjack2', 'detc22', 'detc32', 'chunganh', 'chunganh']
substrings = []

请注意，我为 chunganh 添加了一个欺骗 - 这是我们应该处理的常见边缘情况。

见How do I find the duplicates in a list and create another list with them?

因此要捕获数据中的重复项

seen = {}
dupes = []

for x in data:
    if x not in seen:
        seen[x] = 1
    else:
        if seen[x] == 1:
            dupes.append(x)
        seen[x] += 1

for dupe in dupes:
  substrings.append(dupe)

现在让我们按原样记录数据中的唯一值

# Capture the unique values in the data
last = set(data)

从这里开始，我们可以遍历我们的集合，从每个唯一值的末尾弹出字符。如果我们的集合的长度发生变化，我们就找到了一个唯一的子字符串。

# Handle strings up to 10000 characters long

for k in [0-b for b in range(1, 10000)]:
  # Use negative indexing to start from the longest
  last, middle = set([i[:k] for i in data]), last

  # Unique substring found
  if len(last) != len(middle):
    for k in last:
      count = 0
      for word in middle:
        if k in word:
          count += 1
      if count > 1:
        substrings.append(k)
  # Early stopping
  if len(last) == 1:
    break

最后，您提到只需要长度为 4 的子串。

list(filter(lambda x: len(x) >= 4, substrings))

查找长度 >= 4 的多个最长公共前导子串

Find multiple longest common leading substrings with length >= 4

python

longest-substring