最長の共通部分列を見つけるアルゴリズムを設計しました。これらは手順です：
最初の文字列の最初の文字を選択します。
2 番目の文字列でそれを探し、見つかった場合は、その文字を に追加し、
common_subsequenceその位置を に保存します。そうでない場合は、 の長さと の長indexさを比較し、 大きい場合は、その値を に代入します。common_subsequencelcslcs最初の文字列に戻り、次の文字を選択して、前の手順をもう一度繰り返しますが、今度は
index番目の文字から検索を開始します選択する最初の文字列に文字がなくなるまで、このプロセスを繰り返します。最後に、の値は
lcs最長共通サブシーケンスです。
これは例です:
</p>
X=A, B, C, B, D, A, B
Y=B, D, C, A, B, A
最初の文字列を選択Aします。で
を探します。
2 番目の文字列にがあるので、それを に追加します。
最初の文字列に戻り、次の文字を選択します。今度は の位置から 2 番目の文字列を探します。
の後にあるので、 に B を追加します。
次に、最初の文字列の次の文字を選択します。2 番目の文字列には次の toはありません。したがって、その長さが の長さより大きいため、common_subsequence の値を に割り当てます。最初の文字列の終わりに到達するまで、前の手順を繰り返します。結局の値はAYAcommon_subsequenceBBABAcommon_subsequenceCCBlcslcslcs最長共通部分列です。
このアルゴリズムの複雑さは theta(n*m) です。ここに私の実装があります：
最初のアルゴリズム:
import time
def lcs(xstr, ystr):
if not (xstr and ystr): return # if string is empty
lcs = [''] # longest common subsequence
lcslen = 0 # length of longest common subsequence so far
for i in xrange(len(xstr)):
cs = '' # common subsequence
start = 0 # start position in ystr
for item in xstr[i:]:
index = ystr.find(item, start) # position at the common letter
if index != -1: # if common letter has found
cs += item # add common letter to the cs
start = index + 1
if index == len(ystr) - 1: break # if reached end of the ystr
# update lcs and lcslen if found better cs
if len(cs) > lcslen: lcs, lcslen = [cs], len(cs)
elif len(cs) == lcslen: lcs.append(cs)
return lcs
file1 = open('/home/saji/file1')
file2 = open('/home/saji/file2')
xstr = file1.read()
ystr = file2.read()
start = time.time()
lcss = lcs(xstr, ystr)
elapsed = (time.time() - start)
print elapsed
ハッシュ テーブルを使用した同じアルゴリズム:
import time
from collections import defaultdict
def lcs(xstr, ystr):
if not (xstr and ystr): return # if strings are empty
lcs = [''] # longest common subsequence
lcslen = 0 # length of longest common subsequence so far
location = defaultdict(list) # keeps track of items in the ystr
i = 0
for k in ystr:
location[k].append(i)
i += 1
for i in xrange(len(xstr)):
cs = '' # common subsequence
index = -1
reached_index = defaultdict(int)
for item in xstr[i:]:
for new_index in location[item][reached_index[item]:]:
reached_index[item] += 1
if index < new_index:
cs += item # add item to the cs
index = new_index
break
if index == len(ystr) - 1: break # if reached end of the ystr
# update lcs and lcslen if found better cs
if len(cs) > lcslen: lcs, lcslen = [cs], len(cs)
elif len(cs) == lcslen: lcs.append(cs)
return lcs
file1 = open('/home/saji/file1')
file2 = open('/home/saji/file2')
xstr = file1.read()
ystr = file2.read()
start = time.time()
lcss = lcs(xstr, ystr)
elapsed = (time.time() - start)
print elapsed