使用散列查找字符串内部的重复子字符串

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}