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

Question

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

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

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

longest = [3,1]

我获得此结果的方式是通过计算以下对的最长公共前缀：

• s[15:]，即_be和< code>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

这是一种没有 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:])]

Answer 2

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

让 Python 为你管理内存。不要过早优化。

要获得确切的输出，您可以执行以下操作（如 @agf 建议） :

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

Answer 3

我认为你对副本的担心是没有根据的。请参见下文：

>>> 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 4

下面给出了使用缓冲区的一种方法。然而，可能还有更快的方法。

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

lcp = []
length = len(pos) - 1

for index in range(0, length):
    pre = buffer(s, pos[index])
    cur = buffer(s, pos[index+1], pos[index+1]+len(pre))

    count = 0

    shorter, longer = min(pre, cur), max(pre, cur)

    for i, c in enumerate(shorter):
        if c != longer[i]:
            break
        else:
            count += 1

    lcp.append(count)
    print 

print lcp