查找多个长度大于等于4的最长公共前导子字符串

Question

在Python中，我试图从一个列表中提取至少包含4个字符的所有最长的公共前导子字符串。例如，在下面名为“data”的列表中，符合我的条件的两个最长的公共子字符串是“johnjack”和“detc”。我知道如何用下面的代码找到一个最长的公共子串，因为没有公共子串，所以返回nothing（如预期的那样）。但是我正在努力构建一个脚本来检测列表中的多个公共子字符串，其中每个公共子字符串的长度必须大于等于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添加了一个dupe，这是我们应该处理的常见边缘情况。你知道吗

见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))