python - 长度为 k 的公共(public)子串

Question

我正在尝试编写一个函数，它获取 2 个字符串和一个整数“k”，并返回两个长度为 k 的字符串的公共(public)子字符串。 (如果超过 1 个，则随机返回一个)。网上有很多算法检查最长的公共(public)子串，但我发现没有一个检查 k-length 子串。

如果我想对其进行优化，我认为哈希表是正确的方法，但我不太明白。

我只能编写一个函数来检查列表中是否有超过 1 k 长度的序列。这是我得到的:

def repeat(st, k):
    for i in range(len(st) - k + 1):
        for j in range(i + 1, len(st) - k + 1):
            if st[i : i + k] == st[j : j + k]:
                return st[i : i + k]
    return False

如果有任何帮助，我将不胜感激...:/

Answer 1

简单的版本就是这样:

def common_substr(a, b, k):
  for substr in (a[i:i+k] for i in range(len(a)-k+1)):
    if substr in b:
      return substr

我猜想尤其是对于非常大的输入字符串(例如几兆字节的文本)和大的 k这可能效率太低，并且会构建长度为 k 的所有可能子串的哈希值可以提高速度:

def common_substr(a, b, k):
  substrs = set(a[i:i+k] for i in range(len(a)-k+1))
  for substr in (b[i:i+k] for i in range(len(b)-k+1)):
    if substr in substrs:
      return substr

但我想对此有更聪明的算法。即使是相对简单的strstr() (find string in string) 比每个人都可以实现的直接解决方案更有效。