使用散列在字符串中查找重复的子字符串

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)，如果键不在dict中，则将值设置为0，如果不在dict中，则保持不变。在

不过，还有一些评论：

• 如果找不到任何内容，应该返回None，而不是{}。在
• 不应该调用变量str，因为这是一个内置函数。在
• 您希望迭代j直到字符串的结尾。在
• 如前所述，它只返回一个子字符串，如果它被找到了3次。实际上，您可以使用以前找到的一组子字符串重新编写它：

所以：

^{pr2}$

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')

这样就可以了，我添加了一个内部打印用于调试，在测试后将其删除。在

结果是您请求的子字符串count的dict:）

{'abcd'：1，'ab'：2，'cdb'：1，'dbc'：1，'cdbcab'：1，'cd'：1，'abc'：1，'cdbc'：1，'ca'：1，'db ca'：1，'bc'：2，'dbcab'：1，'db'：1，'cab'：1，'bcdbc'：1，'bcdbca'：1，'cdbca'：1，'cdbcab'：1，'bcdb “：1，'bcd'：1，'abcdb'：1，'bca'：1，'bcdbca'：1}