我有一个元组列表,表示句子中的部分字符串匹配：
[(0,2),(1,(0,4),(2,6),(23,(22,(26,2)]
每个元组的第一个值是匹配的起始位置,第二个值是长度.
我们的想法是折叠列表,以便仅报告最长的继续字符串匹配.在这种情况下,它将是：
[(0,6)]
我不想要最长的范围,比如algorithm to find longest non-overlapping sequences,但是我希望所有的范围都是最长的.
万一你想知道,我正在使用Aho-Corasick的纯python实现来将静态字典中的术语与给定的文本片段进行匹配.
编辑：由于这些元组列表的性质,应单独打印重叠但不是自包含的范围.例如,在字典中使用单词betaz和zeta,betazeta的匹配是[(0,5),(4,8)].由于这些范围重叠,但没有一个包含在另一个中,答案应该是[(0,8)].我还修改了上面的输入数据集,以便涵盖这种情况.
谢谢！
最佳答案
import operator
lst = [(0,2)]
lst.sort(key=operator.itemgetter(1))
for i in reversed(xrange(len(lst)-1)):
start,length = lst[i]
for j in xrange(i+1,len(lst)):
lstart,llength = lst[j]
if start >= lstart and start + length <= lstart + llength:
del lst[i]
break
print lst
#[(0,6)]