Самый длинный общий префикс, использующий буфер?

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

Вот метод без 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:])]

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

Если вы не копируете фрагменты и не оставляете ссылки на копии, я не думаю, что это может вызвать какие-либо проблемы.

---

edit: Есть технические подробности с интернированием строк и тому, что я сам не совсем понимаю.Но я уверен, что фрагмент строки не является всегда копией:

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

Полагаю, ответ, который я пытаюсь дать, состоит в том, чтобы просто позволить python управлять самой памятью,для начала, вы можете посмотреть на буферы памяти и просмотры позже, если это необходимо.И если это уже реальная проблема, возникающая у вас, уточните свой вопрос, подробно опишите, что является настоящей проблемой.

Answer 4

Один из способов использования buffer приведен ниже.Однако, могут быть и более быстрые способы.

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