1

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

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

我只能编写一个函数来检查列表中是否有超过 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

我将不胜感激任何帮助...：/

4

2 回答 2

3

简单的版本就是这样：

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()（在字符串中查找字符串）也比每个人都可以实现的简单的解决方案更有效。

于 2013-05-08T19:20:29.510 回答
1

这绝不是一个有效或聪明的解决方案：

def substrings_of(s, k):
    for i in xrange(0, len(s) - k):
        yield s[i:i+k]

def common_substr(a, b, k):
    for a_s in substrings_of(a, k):
        for b_s in substrings_of(b, k):
            if a_s == b_s:
                return a_s
于 2013-05-08T19:16:52.360 回答