資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用自底向上動態規劃方法查詢最長公共子字串的 Python 程式
當需要使用自底向上動態規劃方法查詢最長公共子字串時，可以定義一個方法來計算較小子問題的解。這些較小子問題的解不需要反覆計算。相反，可以在需要時訪問它們。這將導致開發出針對手邊更大問題的解決方案。
以下是相同內容的演示 -
示例
def compute_lcw(string_1, string_2):
val = [[-1]*(len(string_2) + 1) for _ in range(len(string_1) + 1)]
for i in range(len(string_1) + 1):
val[i][len(string_2)] = 0
for j in range(len(string_2)):
val[len(string_1)][j] = 0
lcw_i = lcw_j = -1
lcw_len = 0
for i in range(len(string_1) - 1, -1, -1):
for j in range(len(string_2)):
if string_1[i] != string_2[j]:
val[i][j] = 0
else:
val[i][j] = 1 + val[i + 1][j + 1]
if lcw_len < val[i][j]:
lcw_len = val[i][j]
lcw_i = i
lcw_j = j
return lcw_len, lcw_i, lcw_j
string_1 = 'bull'
string_2 = 'bullied'
lcw_len, lcw_i, lcw_j = compute_lcw(string_1, string_2)
print("The longest common substring is : ")
if lcw_len > 0:
print(string_1[lcw_i:lcw_i + lcw_len])輸出
The longest common substring is : bull
解釋
- 定義了一個名為“compute_lcw”的方法，該方法將兩個字串作為引數。
- 這兩個字串被迭代並檢查以檢視是否在兩者中都找到了任何匹配的字串。
- 即使找到單個字元，它也會儲存在另一個變數中。
- 當這種情況一直持續到字串的末尾時，這兩個字串將會有另一個公共字串。
- 定義了兩個字串，並透過傳遞這兩個字串來呼叫該方法。
- 此操作的資料被分配給一個變數。
- 然後將其顯示為控制檯上的輸出。
更新於： 2021年3月11日
232 次檢視
廣告