最长公共子串和最长公共子序列

时间:2022-04-13 16:02:39

一、最长公共子串 

  最长公共子串和最长公共子序列                            最长公共子串和最长公共子序列最长公共子串和最长公共子序列

求解左边矩阵对角上连续出现的1的个数也就是求解右边矩阵中的最大值

int longest_common_substring(const char* str1, const char* str2)
{
int len1 = strlen(str1), len2 = strlen(str2);
int *pd = new int[len1];
memset(pd, 0, len1 * sizeof(int));
int maxLen = 0;
for (int i = 0; i < len2; ++i)
{
for (int j = len1 - 1; j >= 0; --j) //从右向左更新,节约空间
{
if (str1[j] == str2[i])
{
if (j == 0)
{
pd[j] = 1;
}
else
{
pd[j] = pd[j - 1] + 1;
}
if (pd[j] > maxLen)
{
maxLen = pd[j];
cout << str1[j];
}
}
else
{
pd[j] = 0;
}
}
}

delete[] pd;
return maxLen;
}


二、最长公共子序列

令dp[m][n]为str1[0,1,..., m-1]和str2[0, 1, ..., n-1]的最长公共子序列的长度,比较str1[m-1]和str2[n-1]

如果str1[m-1]==str2[n-1],那么str1[m-1]属于公共子序列,dp[m][n] = dp[m-1][n-1] + 1;

如果str1[m-1]!=str2[n-1],那么str1[m-1]和str2[n-1]最多只有一个属于公共子序列,dp[m][n] = max(dp[m-1][n], dp[m][n-1]);

当m或n等于0,dp[m][n] = 0;

int longest_common_sequence(const char* str1, const char* str2)
{
int len1 = strlen(str1), len2 = strlen(str2);
int *dp[2];
dp[0] = new int[len1 + 1];
dp[1] = new int[len1 + 1];
memset(dp[0], 0, len1 * sizeof(int));
memset(dp[1], 0, len1 * sizeof(int));

int maxLen = 0;
for (int i = 1; i <= len2; ++i)
{
for (int j = 1; j <= len1; ++j)
{
if (str1[j - 1] == str2[i - 1])
{
dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + 1;
if (dp[i % 2][j] > maxLen) //出现了更大长度长度,更新maxLen并打印出当前字符
{
maxLen = dp[i % 2][j];
cout << str1[j - 1];
}
}
else if (dp[(i - 1) % 2][j] > dp[i % 2][j - 1])
{
dp[i % 2][j] = dp[(i - 1) % 2][j];
}
else
{
dp[i % 2][j] = dp[i % 2][j - 1];
}
}
}
delete[] dp[0];
delete[] dp[1];
return maxLen;
}