贪心算法求字符串的最大公共超串（SCS）

Python

文本编辑器

字符串间以非重叠部分为节点，以重叠部分为边，并存在指向。构成一个完整的图。并使用权重衡量最佳连接路径。

构建求两个字符串，最大重叠片段长度的方法。#a,b belongto V(set of fragments),suffix(a,t)=prefix(b,t)#+-------+-----------------+#|   a   |CGATCGACTCG......|#|   b   |....CGACTCGAGAGTC|#|overlap|    CGACTCG      |#+-------+-----------------+def overlap(a,b,min_length=3):    start=0    while True:        start=a.find(b[:min_length],start)        if start==-1:            return 0        if b.startswith(a[start:]):            return len(a)-start        start+=1通过此方法获得最大重叠片段。

import itertoolsfrom itertools import permutationsdef pick_maximal_overlap(reads,k):    reada,readb=None,None    best_olen=0    for a,b in itertools.permutations(reads,2):        olen=overlap(a,b,min_length=k)        if olen>best_olen:            reada,readb=a,b            best_olen=olen    return reada,readb,best_olen构建此方法来获得，字符串集中的最大重叠字符串对，并移除这两条字符串。添加合并后的字符串。

def greedy_scs(reads,k):    read_a,read_b,olen=pick_maximal_overlap(reads,k)    while olen>0:        reads.remove(read_a)        reads.remove(read_b)        reads.append(read_a+read_b[olen:])        read_a,read_b,olen=pick_maximal_overlap(reads,k)    return ''.join(reads)通过不断的迭代，获得最短的超级串

运行结果如下：SCS(shortest common supperstring)是指包含一个字符串集的最小字符串。字符串集中的字符串为其子串。

对贪心算法的理解。这是一个简单的找钱问题。为的是求得满足找回金额的最小纸币数。