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

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:] 这样的操作中创建多个副本。经过几个小时的搜索，我发现了一个叫 buffer 的函数，它只保留输入字符串的一个副本，但我不太确定在这种情况下最有效的使用方法是什么。有没有什么建议可以实现这个目标？

Answer 1

我觉得你担心复制的问题是多余的。看看下面的内容：

>>> s = "how long is a piece of string...?"
>>> t = s[12:]
>>> print t
a piece of string...?
>>> id(t[0])
23295440
>>> id(s[12])
23295440
>>> id(t[2:20]) == id(s[14:32])
True

除非你在复制切片并且让这些复制的引用到处乱放，否则我觉得这不会造成任何问题。

---

补充：关于字符串内部存储等技术细节，我自己也不是很清楚。但是我可以肯定的是，字符串切片并不总是会是一个复制品：

>>> x = 'google.com'
>>> y = x[:]
>>> x is y
True

我想我想表达的意思是，让Python自己管理内存就好，先不去管这些。需要的话，你可以稍后再看看内存缓冲区和视图。如果这已经是你遇到的一个实际问题，请更新你的问题，详细说明实际遇到的问题是什么。

Answer 2

>>> import os
>>> os.path.commonprefix([s[i:] for i in pos])
'_'

print [len(commonprefix([buffer(s, i) for i in adj_indexes]))
       for adj_indexes in zip(pos, pos[1:])]
# -> [3, 1]

让Python来帮你管理内存，不要过早地进行优化。

为了得到准确的输出，你可以这样做（正如@agf建议的）：

Answer 3

这里有一种方法，不需要使用 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，这是为了应对可能非常长的字符串。

我还忍不住写了这个“一行代码”的方法，它甚至不需要任何索引：

[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:])]