长度为k

Question

的公共子，我想写得到2串和一个整数“K”，并返回长度为k的两个字符串的公共子功能。 （如果超过1，则随机返回一个）。 有很多算法联机检查LONGEST常用子字符串，但我没有发现任何检查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 

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

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 

我想那特别是对于一个非常大的输入字符串（例如， G。文本）和大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()（在字符串中查找字符串）也比每个人都可以实现的直接解决方案更有效。

Answer 2

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

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