python - 多次散列相同的字符

Question

我正在做一个编程挑战，我对其中一个挑战感到疯狂。在挑战中，我需要计算字符串的 MD5。字符串以下列形式给出:

n[c]:其中n是一个数字，c是一个字符。例如:b3[a2[c]] => baccaccacc

一切正常，直到我收到以下字符串:

1[2[3[4[5[6[7[8[9[10[11[12[13[a]]]]]]]]]]]]

这个字符串变成一个有 6227020800 个 a 的字符串。这个字符串超过 6GB，所以在实际时间内几乎不可能计算出来。所以，这是我的问题:

我可以在这里使用 MD5 的任何属性吗？

我知道必须有一种形式可以在短时间内完成，我怀疑它必须与以下事实有关:所有字符串都是相同的字符重复多次。

Answer 1

您可能已经创建了一个(递归)函数来将结果生成为单个值。相反，您应该使用生成器将结果生成为字节流。然后，您可以将这些逐字节输入到您的 MD5 哈希例程中。这样流的大小无关紧要，它只会影响计算时间，而不影响使用的内存。

这是一个使用单 channel 解析器的示例:

import re, sys, md5

def p(s, pos, callBack):
  while pos < len(s):
    m = re.match(r'(d+)[', s[pos:])
    if m:  # repetition?
      number = m.group(1)
      for i in range(int(number)):
        endPos = p(s, pos+len(number)+1, callBack)
      pos = endPos
    elif s[pos] == ']':
      return pos + 1
    else:
      callBack(s[pos])
      pos += 1
  return pos + 1

digest = md5.new()
def feed(s):
  digest.update(s)
  sys.stdout.write(s)
  sys.stdout.flush()

end = p(sys.argv[1], 0, feed)
print
print "MD5:", digest.hexdigest()
print "finished parsing input at pos", end