使用哈希查找字符串中的重复子串

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

print findsubs("abcbc")

Answer 1

你快到了

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, 'cdb': 1, 'dbc': 1, 'cdbcab': 1, 'cd': 1, 'abc': 1, 'cdbc': 1, 'bcab': 1, 'abcdbc': 1, 'ca': 1, 'dbca': 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}

Answer 2

这个大致的想法是可行的。问题在于，如果你在查找字典时找不到某个键，就会出现错误。所以在查找之前，你得先检查这个键是否存在，如果不存在，就要先初始化一下：

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

注意，你可以用 d.setdefault(str[i:j], 0) 来代替 if str[i:j] not in d: d[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