在字符串的合并中，經(jīng)常使用的兩種方式是漢密爾頓路徑和歐拉路徑。本文演示漢密爾頓路徑方式尋求字符串合并的最優(yōu)解。通過貪心算法求出字符串集的1字符串間以非重疊部分為節(jié)點，以重疊部分為邊，并存在指向。構(gòu)成一

在字符串的合并中，經(jīng)常使用的兩種方式是漢密爾頓路徑和歐拉路徑。本文演示漢密爾頓路徑方式尋求字符串合并的最優(yōu)解。通過貪心算法求出字符串集的1字符串間以非重疊部分為節(jié)點，以重疊部分為邊，并存在指向。構(gòu)成一個完整的圖。并使用權(quán)重衡量最佳連接路徑。

構(gòu)建求兩個字符串，最大重疊片段長度的方法

```python

def overlap(a, b, min_length3):

start 0

while True:

start (b[:min_length], start)

if start -1:

return 0

if (a[start:]):

return len(a) - start

start 1

```

通過此方法獲得最大重疊片段。

構(gòu)建找出字符串集中的最大重疊字符串對方法

```python

import itertools

from itertools import permutations

def pick_maximal_overlap(reads, k):

read_a, read_b None, None

best_olen 0

for a, b in (reads, 2):

olen overlap(a, b, min_lengthk)

if olen > best_olen:

read_a, read_b a, b

best_olen olen

return read_a, read_b, best_olen

```

構(gòu)建此方法來獲得字符串集中的最大重疊字符串對，并移除這兩條字符串，添加合并后的字符串。

貪心算法求最短的超級串

```python

def greedy_scs(reads, k):

read_a, read_b, olen pick_maximal_overlap(reads, k)

while olen > 0:

(read_a)

(read_b)

(read_a read_b[olen:])

read_a, read_b, olen pick_maximal_overlap(reads, k)

return ''.join(reads)

```

通過不斷的迭代，獲得最短的超級串。

運行結(jié)果

運行結(jié)果如下：SCS（shortest common supperstring）是指包含一個字符串集的最小字符串。字符串集中的字符串為其子串。

對貪心算法的理解

這是一個簡單的找錢問題。為了求得滿足找回金額的最小紙幣數(shù)。