使用缓冲区的最长公共前缀？

Question

如果我有一个输入字符串和一个数组:

s = "to_be_or_not_to_be" 
pos = [15, 2, 8]

我试图找到pos引用原始数组的连续元素之间的最长公共前缀s.我想获得以下输出:

longest = [3,1]

我获得此方法的方法是计算以下对中最长的公共前缀:

• s[15:]其是_be与s[2:]被_be_or_not_to_be给予3( _be)
• s[2:]其是_be_or_not_to_be与s[8:]被_not_to_be赋予1( _)

但是,如果s是巨大的,我不想在我做类似的事情时创建多个副本s[x:].经过几个小时的搜索,我发现函数缓冲区只维护输入字符串的一个副本,但我不确定在这种情况下在这里使用它的最有效方法是什么.有关如何实现这一目标的任何建议？

Answer 1

这是一种方法，没有buffer它就无法复制，因为它一次只查看一个字符：

from itertools import islice, izip

s = "to_be_or_not_to_be"
pos = [15, 2, 8]


length = len(s)    

for start1, start2 in izip(pos, islice(pos, 1, None)):
    pref = 0
    for pos1, pos2 in izip(xrange(start1, length), xrange(start2, length)):
        if s[pos1] == s[pos2]:
            pref += 1
        else:
            break
    print pref
# prints 3 1

我使用islice, izip, 和xrange以防您谈论的是可能很长的字符串。

我也无法抗拒这个“One Liner”，它甚至不需要任何索引：

[next((i for i, (a, b) in 
    enumerate(izip(islice(s, start1, None), islice(s, start2, None))) 
        if a != b), 
    length - max((start1, start2))) 
 for start1, start2 in izip(pos, islice(pos, 1, None))]

最后一种方法，使用os.path.commonprefix：

[len(commonprefix((buffer(s, n), buffer(s, m)))) for n, m in zip(pos, pos[1:])]