1. 最長(zhǎng)公共子序列（LCS）
1.1 問(wèn)題描述
1.2 思路
利用動(dòng)態(tài)規(guī)劃。
下一步就要找到狀態(tài)之間的轉(zhuǎn)換方程。
因此可以根據(jù)這個(gè)方程來(lái)進(jìn)行填表，以"helloworld"和“l(fā)oop”為例：
1.3 Python代碼
def
LCS
(
string1
,
string2
)
:
len1
=
len
(
string1
)
len2
=
len
(
string2
)
res
=
[
[
0
for
i
in
range
(
len1
+
1
)
]
for
j
in
range
(
len2
+
1
)
]
for
i
in
range
(
1
,
len2
+
1
)
:
for
j
in
range
(
1
,
len1
+
1
)
:
if
string2
[
i
-
1
]
==
string1
[
j
-
1
]
:
res
[
i
]
[
j
]
=
res
[
i
-
1
]
[
j
-
1
]
+
1
else
:
res
[
i
]
[
j
]
=
max
(
res
[
i
-
1
]
[
j
]
,
res
[
i
]
[
j
-
1
]
)
return
res
,
res
[
-
1
]
[
-
1
]
print
(
LCS
(
"helloworld"
,
"loop"
)
)
# 輸出結(jié)果為：
[
[
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
,
0
]
,
[
0
,
0
,
0
,
1
,
1
,
1
,
1
,
1
,
1
,
1
,
1
]
,
[
0
,
0
,
0
,
1
,
1
,
2
,
2
,
2
,
2
,
2
,
2
]
,
[
0
,
0
,
0
,
1
,
1
,
2
,
2
,
3
,
3
,
3
,
3
]
,
[
0
,
0
,
0
,
1
,
1
,
2
,
2
,
3
,
3
,
3
,
3
]
]
,
3
所以"helloworld"和"loop"的最長(zhǎng)公共子序列的長(zhǎng)度為3。
1.4 找到具體的子序列
下面的內(nèi)容借鑒了博主Running07的博客動(dòng)態(tài)規(guī)劃 最長(zhǎng)公共子序列 過(guò)程圖解
如果有兩個(gè)字符串如下：
S1 = “123456778”
S2 = “357486782”
其最終的動(dòng)態(tài)規(guī)劃填表結(jié)果為：
其中S1和S2的LCS并不是只有1個(gè)。
我們根據(jù)遞歸公式：
構(gòu)建了上表，
通過(guò)遞推公式，可以看出，res[i][j]的值來(lái)源于res[i-1][j]或者是res[i-1][j]和res[i][j-1]的較大值（
可能相等
）。
我們將從最后一個(gè)元素c[8][9]倒推出S1和S2的LCS。
res[8][9] = 5，且S1[8] != S2[9]，所以倒推回去，res[8][9]的值來(lái)源于c[8][8]的值(因?yàn)閞es[8][8] > res[7][9])。
res[8][8] = 5, 且S1[8] = S2[8], 所以倒推回去，res[8][8]的值來(lái)源于 res[7][7]。
以此類(lèi)推，如果遇到S1[i] != S2[j] ，且res[i-1][j] = res[i][j-1] 這種存在分支的情況，這里都選擇一個(gè)方向（之后遇到這樣的情況，也選擇相同的方向，要么都往左，要么都往上）。
可得S1和S2的LCS為{3、5、7、7、8}
這是遇見(jiàn)相等的時(shí)候，統(tǒng)一往左走
S1和S2之間還有一個(gè)LCS
這是遇見(jiàn)相等的時(shí)候，統(tǒng)一往上走
：
可得S1和S2的LCS為{3、4、6、7、8}
2. 最長(zhǎng)公共子串
2.1 問(wèn)題描述
2.2 思路
和最長(zhǎng)公共子序列一樣，使用動(dòng)態(tài)規(guī)劃的算法。
下一步就要找到狀態(tài)之間的轉(zhuǎn)換方程。
和LCS問(wèn)題唯一不同的地方在于當(dāng)A[i] != B[j]時(shí)，res[i][j]就直接等于0了，因?yàn)樽哟仨氝B續(xù)，
且res[i][j] 表示的是以A[i]，B[j]截尾的公共子串的長(zhǎng)度
。因此可以根據(jù)這個(gè)方程來(lái)進(jìn)行填表，以"helloworld"和“l(fā)oop”為例：
這個(gè)和LCS問(wèn)題還有一點(diǎn)不同的就是，需要設(shè)置一個(gè)res，每一步都更新得到最長(zhǎng)公共子串的長(zhǎng)度。
2.3 Python代碼
def
LCstring
(
string1
,
string2
)
:
len1
=
len
(
string1
)
len2
=
len
(
string2
)
res
=
[
[
0
for
i
in
range
(
len1
+
1
)
]
for
j
in
range
(
len2
+
1
)
]
result
=
0
for
i
in
range
(
1
,
len2
+
1
)
:
for
j
in
range
(
1
,
len1
+
1
)
:
if
string2
[
i
-
1
]
==
string1
[
j
-
1
]
:
res
[
i
]
[
j
]
=
res
[
i
-
1
]
[
j
-
1
]
+
1
result
=
max
(
result
,
res
[
i
]
[
j
]
)
return
result
print
(
LCstring
(
"helloworld"
,
"loop"
)
)
# 輸出結(jié)果為：2
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
