string - 2 つの文字列間の冗長な一致を削除するには?

Question

2 つの文字列 str1 と str2 が与えられた場合、[str1_beg, str1_end, str2_beg, str2_end] の形式で、共有部分文字列を間隔として記述した一致のリストがあります。マッチからの str1_beg、str1_end および str2_beg、str2_end が他のマッチに埋め込まれている冗長なマッチを削除したいと考えています。

Answer 1

[beg_index, end_index] ごとに [beg_index_new, end_index_new] を見つけ、end_index < end_index_new および beg_index >= beg_index_new を満たすものを削除します。

それがO(n^2)

Answer 2

まず第一に、マッチをより効率的に保存できます。

[str_beg,str2_beg,match_len]

これにより、冗長性のチェックも非常に簡単になります。たとえば、

for match in matches:
  for i in xrange(len(matches)):
    if matches[i][:2] == match[:2] and mathches[i][2] < match[2]:
      del matches[i]

マッチのリストは、matches という変数に割り当てられ、上で提案した構造を持っていると仮定しているので、ma. <= 演算子ではなく < 演算子を使用しています。これらが等しい場合、それらはまったく同じ一致であり、同じ一致が 2 回行われることはないと想定しているためです。両方の matche の [:2] スライスをチェックしている場合、それらのリストの最初の 2 つの要素 (開始位置) をチェックしています。