使用自底向上動態規劃方法查詢最長公共子字串的 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 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

開始
廣告