1、求最長公共子串的長度

問題描述：有兩個字符串str和str2，求出兩個字符串中最長公共子串長度。str=acbcbcef，str2=abcbced，則str和str2的最長公共子串為bcbce，最長公共子串長度為5。

算法思路：

把兩個字符串分別以行和列組成一個二維矩陣。

比較二維矩陣中每個點對應行列字符中否相等，相等的話值設置為1，否則設置為0。

通過查找出值為1的最長對角線就能找到最長公共子串。

針對于上面的兩個字符串我們可以得到的二維矩陣如下：

從上圖可以看到，str1和str2共有5個公共子串，但最長的公共子串長度為5。

為了進一步優化算法的效率，我們可以再計算某個二維矩陣的值的時候順便計算出來當前最長的公共子串的長度，即某個二維矩陣元素的值由record[i][j]=1演變為record[i][j]=1 +record[i-1][j-1]，這樣就避免了后續查找對角線長度的操作了。修改后的二維矩陣如下：

C++代碼實現如下:

string getLCS(string str1, string str2) {vector<vector<int> > record(str1.length(), vector<int>(str2.length()));int maxLen = 0, maxEnd = 0;for(int i=0; i<static_cast<int>(str1.length()); ++i)for (int j = 0; j < static_cast<int>(str2.length()); ++j) {if (str1[i] == str2[j]) {if (i == 0 || j == 0) {record[i][j] = 1;}else {record[i][j] = record[i - 1][j - 1] + 1;}}else {record[i][j] = 0;}if (record[i][j] > maxLen) {maxLen = record[i][j];maxEnd = i; //若記錄i,則最后獲取LCS時是取str1的子串}}return str1.substr(maxEnd - maxLen + 1, maxLen); }

?2、返回最長公共子串

??所謂動態規劃思想就是認為大問題可以被拆分成小問題。它一般有3個性質:

• 1、無論是總問題還是子問題都存在最優解。
• 2、某問題只取決于它的子問題，和由它組成的問題沒關系。
• 3、各子問題之間大多是相互關聯的。

它每一階段都有各個子問題的最優解，各子問題的最優解，會產生往往會重復計算，于是用一個表把它們存儲起來。具體到本問題就是每一個字符的相同，然后逐步到原來問題的解。本問題的解是兩個字符串的最長公共子串，那么它的子問題的解的極限是1個字符是否相同。在解集中每個單元格的左上角的單元格就是前面相鄰的兩個字符是否相同。并且如果該單元格對應的下標不同，那么單元格可以立刻被置0.否則它就應該加上左上角的單元格中的解的值。?應用動態規劃算法以后時間復雜度變成了O(n^2)。

package com.company;public class Solution {static public String findLongestCommonSubstring0(String string0,String string1) {int[][] answerArray = new int[string0.length()][string1.length()];int maxSubstringLength = 0;int startLongestIndex = 0;for (int counter = 0;counter < string0.length();counter++) {for (int counter0 = 0;counter0 < string1.length();counter0++) {if (string0.charAt(counter) == string1.charAt(counter0)) {if (counter - 1 >= 0 && counter0 - 1 >= 0)answerArray[counter][counter0] = answerArray[counter - 1][counter0 - 1] + 1;else answerArray[counter][counter0] = 1;if (answerArray[counter][counter0] > maxSubstringLength) {maxSubstringLength = answerArray[counter][counter0];startLongestIndex = counter - maxSubstringLength + 1;}} else answerArray[counter][counter0] = 0;}}return string0.substring(startLongestIndex,startLongestIndex + maxSubstringLength);} }

?

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的动态规划—最长公共子串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。