題目：找出兩個(gè)字符串的最長公共字串，例如字符串“abccade”與字符串“dgcadde”的最長公共子串為“cad”。
分析：動(dòng)態(tài)規(guī)劃法。通過把中間的比較結(jié)果記錄下來，從而可以避免字符的重復(fù)比較。：
首先定義二元函數(shù)（i，j）：表示分別以s1[i],s2[j]結(jié)尾的公共子串的長度，顯然，f（0， j） = 0 (j >= 0),f(i, 0) = 0(i >= 0),那么對(duì)于f(i +1, j + 1)而言，則有如下兩種取值：
（1) f(i + 1, j +1) = 0,當(dāng)str1[i + 1] != str2[j + 1]時(shí)
（2）f(i + 1, j +1) = f(i, j) + 1,當(dāng)str1[i + 1] == str2[j + 1]時(shí)
根據(jù)這個(gè)公式可以計(jì)算出f(i, j)（0<= i<=len(s1), 0 <= j <= len(s2)，所有的值，從而可以找出最長的子串。
def getMaxSubStr(str1, str2):
? ? len1 = len(str1)
? ? len2 = len(str2)
? ? sb = ''
? ? maxs = 0? # 用來記錄最長公共子串的長度
? ? maxI = 0? # 用來記錄最長公共字串最后一個(gè)字符的位置
? ? # 申請(qǐng)新的空間來記錄公共字串長度信息
? ? M = [([None] * (len1 + 1)) for i in range(len2 + 1)]
? ? i = 0
? ? while i < len1 + 1:
? ? ? ? M[i][0] = 0
? ? ? ? i += 1
? ? j = 0
? ? while j < len2 + 1:
? ? ? ? M[0][j] = 0
? ? ? ? j += 1
? ? # 通過利用遞歸公式填寫新建得二維數(shù)組（公共字串得長度信息）
? ? i = 1
? ? while i < len1 + 1:
? ? ? ? j = 1
? ? ? ? while j < len2 + 1:
? ? ? ? ? ? if list(str1)[i - 1] == list(str2)[j - 1]:
? ? ? ? ? ? ? ? M[i][j] = M[i - 1][j - 1] + 1
? ? ? ? ? ? ? ? if M[i][j] > maxs:
? ? ? ? ? ? ? ? ? ? maxs = M[i][j]
? ? ? ? ? ? ? ? ? ? maxI = i
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? M[i][j] = 0
? ? ? ? ? ? j += 1
? ? ? ? i += 1
? ? i = maxI - maxs
? ? while i < maxI:
? ? ? ? sb = sb + list(str1)[i]
? ? ? ? i += 1
? ? return sb
if __name__ == "__main__":
? ? str1 = 'abccade'
? ? str2 = 'dgcadde'
? ? print(getMaxSubStr(str1, str2))
程序運(yùn)行結(jié)果：
cad
