[算法筆記]動態規劃之最長公共子串和最長公共子序列

DandJ 發布于2019-07-30 15:40 / 561人閱讀

摘要：源代碼管理中，指令，可以查找出編輯前后文件的差異，這是基于動態規劃實現的。編輯距離，判斷字符串的相似程度，也是基于動態規劃計算。

本文是《算法圖解》筆記

應用場景

一切脫離實際應用場景的算法都是耍流氓！

生物學家根據最長公共序列來確定 DNA 鏈的相似性，進而判斷兩種動物或疾病有多相似。最長公共序列還被用來尋找多發性硬化癥治療方案。

源代碼管理中，git diff指令，可以查找出編輯前后文件的差異，這是基于動態規劃實現的。

編輯距離（levenshtein distance），判斷字符串的相似程度，也是基于動態規劃計算。可以通過這個技術從拼寫檢查到判斷用戶上傳的資料是否是盜版。（這樣看來，我猜想大學論文查重應該也是基于動態規劃算法:P）

Microsoft Word等軟件中具有斷字功能，使用動態規劃可以確定什么地方斷字以確保行長一致。

最長公共子串

場景：

某個用戶在網站搜索框中輸入一個字符串 hish，但其實用戶想輸入的是 fish

介紹這個網站的可選字典里面只有 fish 和 vista 這兩個相似單詞

猜測用戶到底想要搜索的是什么字符串？

在動態規劃中，目標是要將某個指標最大化，在這個例子中，要找出兩個單詞的公共子串。更大的那個即為結果。

求解網格：

注：只列出hish的例子，vista思路相同

	h	i	s	h
f	0	0	0	0
i	0	1	0	0
s	0	0	2	0
h	1	0	0	3

算法描述：

如果兩個字母不同，值為0

如果兩個字母相同，值為左上角鄰居的值加一

偽代碼：

if word_a[i] == word_b[j]:
    cell[i][j] = cell[i-1][j-1] + 1
else:
    cell[i][j] = 0

最長公共子序列

場景

假設用戶不小心輸入了 fosh ，要判斷他原本要輸入的是 fish 還是 fort

這時候需要使用最長公共子序列來比較

求解網絡：

	f	o	s	h
f	1	1	1	1
i	1	1	1	1
s	1	1	2	2
h	1	1	2	3

算法描述:

如果兩個字母不同，就選擇上方和左方鄰居格子中較大的那個值

如果兩個字母相同，值為左上方格子中的值加一

偽代碼：

if word_a[i] == word_b[j]:
    cell[i][j] = cell[i-1][j-1] + 1
else:
    cell[i][j] = max(cell[i-1][j], cell[i][j-1])

我的博客： http://vimiix.com

云服務器 GPU云服務器最長公共子串最長公共子序列最大公共子串算法 java最長相同子串

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/41397.html

動態規劃問題（2）——尋找最長公共子串

摘要：題目給定兩個字符串求出它們的最長公共字串說明比如在單詞和它們的最長公共子序列是。最長公共子串和最長公共子序列的區別。題目給定兩個字符串,求出它們的最長公共字串 var str1=abcdefg; var str2=xyzabcd; 說明：比如在單詞abcdefg和abcdefg它們的最長公共子序列是abcd。尋找最長子序列常用于遺傳學中，用于使用核苷酸堿基的首字母對DNA的描述（這...

wushuiyong 2019-08-21 11:27 評論0 收藏0
算法設計 - LCS 最長公共子序列&&最長公共子串 &&LIS 最

摘要：若且，則是和的最長公共子序列若且，則是和的最長公共子序列。遞歸結構容易看到最長公共子序列問題具有子問題重疊性質。例如，在計算和的最長公共子序列時，可能要計算出和及和的最長公共子序列。雖是讀書筆記，但是如轉載請注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復制黨本章講解： 1. LCS（最長公共子序列）O(n^2)的時間復雜...

weizx 2019-08-14 12:07 評論0 收藏0
字符串處理文章outline

摘要：遇到問題查查，看看，大神的講解問問島胖君下面是我最近整理出來的關于字符串的文章的怎么翻譯匯集目錄非常希望強化博客的功能，比如分類，置頂。雖是讀書筆記，但是如轉載請注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復制黨最近在看算法和語言，基本屬于看知識 --> java實現 --> 整理blog 這個路線。遇到問題查查st...

Karuru 2019-08-14 15:07 評論0 收藏0
[算法總結] 搞定 BAT 面試——幾道常見的子符串算法題

摘要：第一種方法常規方法。如果不存在公共前綴，返回空字符串。注意假設字符串的長度不會超過。說明本題中，我們將空字符串定義為有效的回文串。示例輸入輸出一個可能的最長回文子序列為。數值為或者字符串不是一個合法的數值則返回。說明本文作者：wwwxmu 原文地址:https://www.weiweiblog.cn/13s... 作者的博客站點：https://www.weiweiblog.c...

chanjarster 2019-08-19 11:07 評論0 收藏0
javascript 最長公共子序列

摘要：但不是和的最長公共子序列，而序列和也均為和的最長公共子序列，長度為，而和不存在長度大于等于的公共子序列。最長公共子序列給定序列和，從它們的所有公共子序列中選出長度最長的那一個或幾個。為和的最長公共子序列長度。最長公共子序列（Longest Common Subsequence LCS）是從給定的兩個序列X和Y中取出盡可能多的一部分字符，按照它們在原序列排列的先后次序排列得到。LCS問...

Xufc 2019-08-22 13:52 評論0 收藏0