長度爲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