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

給定兩個字符串str1和str2我有一個描述共享子字符串的匹配列表，其格式爲[str1_beg，str1_end，str2_beg，str2_end]。我想刪除多餘的匹配，其中匹配的str1_beg，str1_end和str2_beg，str2_end嵌入其他一些匹配中。如何刪除兩個字符串之間的多餘匹配？

來源

2012-09-14 maasha

如果我需要循環所有匹配，並且通過所有匹配的每個匹配循環來確定匹配是否嵌入，它會變得很慢。先排序如何？ – maasha

對於每個[beg_index，end_index]找到[beg_index_new，end_index_new]並刪除滿足end_index < end_index_new和beg_index> = beg_index_new的那些。

這就是O（n^2）

來源

2012-09-14 12:19:33 nullpotent

首先，您可以更有效地存儲您的匹配。

[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]切片，我是他們的名單的頭兩個元素，這是首發職位的國王。

來源

2012-09-14 12:26:33 bigblind

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

回答

相關問題