給定兩個(gè)字符串和一個(gè)窗口大小 k：找到具有約束的最長公共子序列。約束是：公共子序列中的相鄰元素在一個(gè)k窗口內(nèi)（理想情況下，該約束適用于兩個(gè)輸入字符串。但如果可以滿足第二個(gè)字符串就可以了）例如：A = "carpani"B = "blarpan sharlie paneaui"k = 3輸出：arpan（不是 arpani）。有人可以告訴我如何解決這個(gè)問題嗎？如果有人可以發(fā)布偽代碼，那就太好了。
1 回答
胡說叔叔
TA貢獻(xiàn)1804條經(jīng)驗(yàn) 獲得超8個(gè)贊
這是一個(gè)動(dòng)態(tài)規(guī)劃問題。它們可以通過兩種基本方式解決。一種是寫一個(gè)遞歸函數(shù)，然后memoize。另一種是自底向上構(gòu)建數(shù)據(jù)結(jié)構(gòu)。
自上而下的方法通常更容易編寫。自下而上的方法通常更有效。這就是為什么兩者都要學(xué)習(xí)的原因。
我將在 Python 中演示自上而下的方法。
考慮以下功能：
def best_k_match_ending_at(string1, string2, k, i, j):
if string1[i] != string2[j]:
return (0, None, None)
else:
best = (0, None, None)
for i_old in range(max(i-k, 0), i):
for j_old in range(max(j-k, 0), j):
this = best_k_match_ending_at(string1, string2, k, i_old, j_old)
best = max(best, this)
return (best[0] + 1, (i, best[1]), (j, best[2]))
def best_k_match(string1, string2, k):
best = (0, None, None)
for i in range(len(string1)):
for j in range(len(string2)):
best = max(best, best_k_match_ending_at(string1, string2, k, i, j))
return best
# prints (5, (5, (4, (3, (2, (1, None))))), (6, (5, (4, (3, (2, None)))))
print(best_k_match('carpani', 'blarpan sharlie paneaui', 3))
這是非常低效的。但正確?，F(xiàn)在記憶它之前的一步。我喜歡重構(gòu)以將輔助函數(shù)移動(dòng)到主函數(shù)中。邏輯是一樣的，但是當(dāng)我記憶時(shí)，它會(huì)告訴我何時(shí)處理完數(shù)據(jù)。
def best_k_match(string1, string2, k):
def best_ending_at(i, j):
if string1[i] != string2[j]:
return (0, None, None)
else:
best = (0, None, None)
for i_old in range(max(i-k, 0), i):
for j_old in range(max(j-k, 0), j):
this = best_ending_at(i_old, j_old)
best = max(best, this)
return (best[0] + 1, (i, best[1]), (j, best[2]))
best = (0, None, None)
for i in range(len(string1)):
for j in range(len(string2)):
best = max(best, best_ending_at(i, j))
return best
print(best_k_match('carpani', 'blarpan sharlie paneaui', 3))
現(xiàn)在我記住了
def best_k_match(string1, string2, k):
memoized = {}
def best_ending_at(i, j):
if string1[i] != string2[j]:
return (0, None, None)
elif (i, j) not in memoized:
best = (0, None, None)
for i_old in range(max(i-k, 0), i):
for j_old in range(max(j-k, 0), j):
this = best_ending_at(i_old, j_old)
best = max(best, this)
memoized[(i, j)] = (best[0] + 1, (i, best[1]), (j, best[2]))
return memoized[(i, j)]
best = (0, None, None)
for i in range(len(string1)):
for j in range(len(string2)):
best = max(best, best_ending_at(i, j))
return best
print(best_k_match('carpani', 'blarpan sharlie paneaui', 3))
現(xiàn)在這很有效，但您可能不太喜歡輸出。因?yàn)樗且粋€(gè)倒序的鏈表。這是一個(gè)更好的輸出。
def best_k_match(string1, string2, k):
memoized = {}
def best_ending_at(i, j):
if string1[i] != string2[j]:
return (0, None, None)
elif (i, j) not in memoized:
best = (0, None, None)
for i_old in range(max(i-k, 0), i):
for j_old in range(max(j-k, 0), j):
this = best_ending_at(i_old, j_old)
best = max(best, this)
memoized[(i, j)] = (best[0] + 1, (i, best[1]), (j, best[2]))
return memoized[(i, j)]
best = (0, None, None)
for i in range(len(string1)):
for j in range(len(string2)):
best = max(best, best_ending_at(i, j))
# Turn linked lists to something nicer.
best_seq_rev = []
best_match_rev = []
best_link_1 = best[1]
best_link_2 = best[2]
while best_link_1 is not None:
best_seq_rev.append(string1[best_link_1[0]])
best_match_rev.append((best_link_1[0], best_link_2[0]))
best_link_1 = best_link_1[1]
best_link_2 = best_link_2[1]
best_seq = "".join(reversed(best_seq_rev))
best_match = list(reversed(best_match_rev))
return (best[0], best_seq, best_match)
# prints (5, 'arpan', [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6)])
print(best_k_match('carpani', 'blarpan sharlie paneaui', 3))
如果字符串的長度為n和m，則為O(n*m*k^2)。
添加回答
舉報(bào)
0/150
提交
取消