string - 如何删除两个字符串之间的冗余匹配？

Question

给定两个字符串 str1 和 str2，我有一个匹配列表，将共享子字符串描述为 [str1_beg, str1_end, str2_beg, str2_end] 形式的间隔。我想删除冗余匹配，其中 str1_beg、str1_end 和 str2_beg、str2_end 从匹配中嵌入到其他匹配中。

Answer 1

首先，您可以更有效地存储匹配项。

[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]

我假设您的匹配列表被分配给一个名为匹配的变量，并且具有我上面提出的结构，所以 ma. 我使用的是 < 运算符而不是 <= 运算符，因为在它们相等的情况下，它们是完全相同的匹配，我假设您不会有两次相同的匹配。在我检查两个 matche 的 [:2] 切片的地方，我检查了它们列表的前 2 个元素，它们是起始位置。

Answer 2

对于每个 [beg_index, end_index] 找到 [beg_index_new, end_index_new] 并删除满足 end_index < end_index_new 和 beg_index >= beg_index_new 的那些。

那是 O(n^2)