python字典理解可以用来创建子字符串及其位置的字典吗？

Question

给定一个字符串，我想创建一个包含字符串中所有n个字符的子字符串的字典，其中dictionary键是子字符串，值是一个列表。列表的第一个元素是子字符串的出现次数，列表的第二个元素是这些引用的起始位置列表。在

例如，对于n=3，字符串'abcdabcxdabc'将在该字典中产生：

{'abc': [3, [0, 4, 9]], 
 'cda': [1, [2]], 
 'dab': [2, [3, 8]], 
 'bcd': [1, [1]], 
 'cxd': [1, [6]], 
 'bcx': [1, [5]], 
 'xda': [1, [7]]}

下面的代码是有效的，因为它只遍历字符串一次，但是我想知道是否有更优雅和/或更像python的方法来完成这项工作，也许使用字典理解。我对python相当陌生，仍在试图弄清楚什么时候使用理解是有意义的（甚至是可能的），等等

^{pr2}$

更新：谢谢你的回复。它们通常证实了我的怀疑，即这太复杂了，不可能在一个单一的理解中有效地实现（但多亏了volcano，它证明了如果不考虑效率，这是可能的）。感谢RemcoGerlich和Ignacio Vazquez Abrams将我引向defaultdict。我得再深入一点。我的计时结果表明，与dict相比，初始化defaultdict的开销要大一些，但运行时间可能会稍快一些，至少在本例中是这样。（计时结果发表在下面的单独评论中）现在我想知道是否有任何情况下dict会比defaultdict更受欢迎。还有，感谢纳科莱给我指出了它的作用时间。在

Answer 1

这很可怕，但是（我只添加了偏移量，从偏移量列表中可以得到的出现次数）。是的，也许可以

In [83]: my_str = 'abcdabcxdabc'

In [84]: n=3

In [85]: {substr: [my_str.replace(substr, ' '*n, c).index(substr) 
                   for c in xrange(my_str.count(substr))]
   ....: for substr in set(my_str[idx:idx+n] for idx in xrange(len(my_str)-n))}
Out[85]: 
{'abc': [0, 4, 9],
 'bcd': [1],
 'bcx': [5],
 'cda': [2],
 'cxd': [6],
 'dab': [3, 8],
 'xda': [7]}

Answer 2

正如@Ignacio所说，任何试图解决这个问题的理解都将有一个二次运行时性能，如@volcano的答案所示。最干净的解决问题的方法是这样的：

def substrings(text, n):
    d = collections.defaultdict(list)
    for i in xrange(len(text)-n+1):
        d[text[i:i+n]].append(i)
    return d

请注意，您不需要存储子字符串的数量，因为您可以通过len(d['abc'])来获得abc的出现次数。在

以下是这种方法与综合方法的一些时间安排：

^{pr2}$

请注意，当输入的大小增加100倍时，理解的时间会增加1000倍。在

Answer 3

问题是v[0]依赖于长度或{}，这意味着生成v[1]的操作必须操作两次，或者为了填充{}来替换第一次包含的伪值，必须对字典进行迭代。在

另一个问题是dict comprehension期望整个键和值立即可用，这意味着您必须运行一个list comprehension来获取字符的所有索引，这意味着整个操作变成O（n²）。在

我要做的唯一优化是替换d的创建，这样您就不需要检查密钥包含了。在

d = collections.defaultdict(lambda: [0, []])