バッファを使用する最も長い共通プレフィックス？

Question

私は入力文字列と配列している場合：私は、元sを参照配列posの連続する要素間の最長の共通のプレフィックスを見つけようとしています

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

を。私は次の出力を取得しようとしています：私はこれを得

longest = [3,1] 

方法は、次のペアの最長の共通のプレフィックスを計算することである：

_be_or_not_to_beは3を与えている _beと s[2:]ある

• s[15:] 1（_）を与える_not_to_beで_be_or_not_to_beとs[8:]ある（_be）
• s[2:]

しかし、sが巨大な場合は、s[x:]のようにすると複数のコピーを作成したくありません。数時間の検索の後、私は入力文字列のコピーを1つだけ保持する関数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

あなたのコピーについてのあなたの心配は根拠がないと思います。以下を参照してください：

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

bufferを使用する1つの方法は以下のとおりです。しかし、はるかに速い方法があるかもしれません。

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 

Answer 4

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

あなたのためのメモリを管理するためのPythonをしてみましょう。途中で最適化しないでください。あなたは（@agf suggestedとして）行うことができ、正確な出力を得るために

：それは一度に一つの文字を見てここで

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