首页 > 代码库 > 动态规划--最长公共子串

动态规划--最长公共子串

2024-07-21 07:55:50   217人阅读

最长公共子串也是一个动态规划的问题，先求出子问题的解，然后才能求出最优解。

首先我们来看设X = <x1, x2, ..., xm>, Y= <y1, y2, ..., yn>，设C[i][j]为串 Xi 和 Yj 的最长公共子串长度，则

  • C[i][j]  =  C[i-1][j-1] +1,  Xi == Yj
  • C[i][j]  =  0,  Xi != Yj

申请一个m*n的数组，同时计算出该数组对应位置的数值，找出最大值，则为X 和 Y最长公共子串。

代码如下：

 1 // LCS(SubString).cpp : 定义控制台应用程序的入口点。 2 // 3  4 #include <iostream> 5 #include <string> 6 using namespace std; 7  8  9 int LengthOfLongestSubString(const string &X, const string &Y)10 {11     // 使元素从下标0开始存储，方便数组访问12     string strX = " " + X, strY = " " +Y;13     int m = strX.size(), n = strY.size();14     int maxLength = 0;15 16     int **c = new int*[m];17 18     for (int i = 0; i < m; ++i)19         c[i] = new int[n];20     // init the cases that i = 0 and j = 021     for (int i = 0; i < m; ++i)22         c[i][0] = 0;23     for (int i = 0; i < n; ++i)24         c[0][i] = 0;25 26     // Calculate the array C27     for (int i = 1; i < m; i++)28         for (int j = 1; j < n; ++j)29         {30             if (X[i] == Y[j])31             {32                 c[i][j] = c[i - 1][j - 1] + 1;33                 if (c[i][j] > maxLength)34                     maxLength = c[i][j];35             }36             else37                 c[i][j] = 0;38         }39     // Free the memory40     for (int i = 0; i < m; ++i)41         delete c[i];42     delete []c;43     44     return maxLength;45 }46 47 48 int main(int argc, char** argv)49 {50     const string X = "ABCDEFDBEFG";51     const string Y = "DKGDBCDEFAB";52 53     int Length = LengthOfLongestSubString(X, Y);54     cout << "The max Length is :" << Length << endl;55     56     return 0;57 }

 

动态规划--最长公共子串


联系
我们