使用散列查找字符串內部的重複子字符串

Question

給定問題：在字符串中查找重複的子字符串，是否可以使用散列？我想創建一個字典，其中子字符串作爲鍵和重複實例的數量作爲值。這是我到目前爲止。我收到一個錯誤，因爲我使用了一個子字符串作爲字典的關鍵字。任何人都能發現我的錯誤嗎謝謝！！！

def findsubs(str): 
    d={} 
    for i in range(len(str)-1): 
    for j in range(i+2, len(str)-2): 
     if d[str[i:j]]>1: 
     return str[i:j] 
     else: 
     d[str[i:j]] = d[str[i:j]] +1 

    return 0 

打印findsubs（ 「abcbc」）

Answer 1

的總體思路應該工作。只是，如果在查找字典時沒有在字典中找到密鑰，則會發生錯誤 - 因此在查找前必須檢查密鑰是否存在，如果密鑰沒有，則需要進行初始化：

def findsubs(str): 
    d={} 
    for i in range(len(str)-1): 
    for j in range(i+2, len(str)-2): 
     if str[i:j] not in d: 
     d[str[i:j]] = 0 

     if d[str[i:j]]>1: 
     return str[i:j] 
     else: 
     d[str[i:j]] = d[str[i:j]] +1 

    return 0 

注意，代替if str[i:j] not in d: d[str[i:j]] = 0，你可以做d.setdefault(str[i:j], 0)，這將值設置爲0如果該鍵不在字典，並離開它，如果沒有改變它。

一些更多的評論，但：

• 您應該返回None，不0，如果你沒有發現任何東西。
• 您不應該調用變量str，因爲這是一個內置函數。
• 你想迭代j直到字符串結束。
• 如寫，它只會返回一個子字符串，如果它被發現3次。真正使用一組先前發現的子串，而不是可以重新寫：

所以：

def findsubs(s): 
    found = set() 
    for i in range(len(s)-1): 
    for j in range(i+2, len(s)+1): 
     substr = s[i:j] 
     if substr in found: 
     return substr 
     found.add(substr) 

    return None 

Answer 2

你幾乎有

def findsubs(instr): 
    d={} 
    for i in range(len(instr)): 
    for j in range(i+2, len(instr)+1): 
     print instr[i:j] 
     d[instr[i:j]] = d.get(instr[i:j],0) + 1 
    return d  

instr = 'abcdbcab' 
print instr 
print findsubs('abcdbcab') 

這將工作，我添加了一個打印內部用於調試目的，請在測試後將其刪除。

結果與子數量有你問:)

{ 'ABCD' 的字典：1， 'AB'：2， '國開行'：1， 'DBC'：1，「cdbcab '：1，'cd'：1，'abc'：1，'cdbc'：1，'bcab'：1，'abcdbc'：1，'ca'：1，'db ca'：1，'bc '：2，'dbcab'：1，'db'：1，'cab'：1，'bcdbcab'：1，'bcdbc'：1，'abcdbca'：1，'cdbca'：1，'abcdbcab'： 1，'bcdb '：1，'bcd'：1，'abcdb'：1，'bca'：1，'bcdbca'：1}