如何刪除兩個字符串之間的多餘匹配？

Question

給定兩個字符串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] 

我假設你匹配列表被分配到一個名爲匹配的變量，並有我提出的結構以上，所以馬。我使用的是<運算符，而不是< =運算符，因爲如果它們相等，則它們完全相同，我假設您不會有兩次相同的匹配。 我在哪裏檢查matche的[：2]切片，我是他們的名單的頭兩個元素，這是首發職位的國王。