C++ 笔试之基础 08 求两个字符串的最长公共子串，最长公共子序列，编辑距离

(1)    找出两个字符串的最长公共子串

题目：输入两个字符串，找出两个字符串中最长的公共子串。

找两个字符串的最长公共子串，这个子串要求在原字符串中是连续的。因此我们采用一个二维矩阵来存储中间结果，下面我们看这个二维数组如何构造？

假设两个字符串分别是：”bab”和”caba”。

如果str[i] == str[j] 则matrix[i][j] = 1，否则matrix[i][j] = 0

然后我们从矩阵中找出斜对角线最长的那个子字符串，就是最长公共子串。

即”ab”和”ba”分别为2。

我们可以简化一下，在当我们计算matrix[i][j]时，我们判断str[i] == str[j] 和matrix[i-1][j-1]。

如果str[i] == str[j]，则matrix[i][j] = matrix[i-1][j-1] + 1；否则matrix[i][j] = 0。

如下图所示：

所以此时，我们只是将matrix[M][N]中，找到最大的值，即为最长公共子串。

然后我们还可以简化一下空间复杂度。

因为我们每判断一个matrix[i][j]时，实际上它只与matrix[i-1][j-1]相关。故所以我们可以使用一维数组来保存上一次的结果。

实现代码如下：

[cpp] view plain copy

1. #include <cstring>  
2. #include <iostream>  
3. using namespace std;  
4.   
5. int GetLongestCommonSubString(const char *pStr1, const char *pStr2)  
6. {  
7.     /* 判断参数合法性 */  
8.     if (pStr1 == NULL || pStr2 == NULL)  
9.     {  
10.         return -1;  
11.     }  
12.   
13.     int n = strlen(pStr1);  
14.     int m = strlen(pStr2);  
15.     int longestCommonSubString = 0;  
16.   
17.     /* 申请辅助空间，并初始化为0 */  
18.     int *LCS = new int[m];  
19.     for (int i = 0; i < m; i++)  
20.     {  
21.         LCS[i] = 0;  
22.     }  
23.   
24.     /* 不断判断pStr[i] ?= pStr[j]，然后根据不同情况来更新LCS */  
25.     for (int i = 0; i < n; i++)  
26.     {  
27.         for (int j = m - 1; j >= 0; j--)  
28.         {  
29.             if (pStr1[i] == pStr2[j])   /* 如果pStr1[i] == pStr2[j]，LCS[j] = LCS[j-1] + 1 */  
30.             {  
31.                 if (j == 0)  
32.                 {  
33.                     LCS[j] = 1;  
34.                 }  
35.                 else  
36.                 {  
37.                     LCS[j] = LCS[j-1] + 1;  
38.                 }  
39.             }  
40.             else                        /* 如果pStr1[i] != pStr2[j]，LCS[j] = 0 */  
41.             {  
42.                 LCS[j] = 0;  
43.             }  
44.   
45.             /* 更新最长子串的长度 */  
46.             if (LCS[j] > longestCommonSubString)  
47.             {  
48.                 longestCommonSubString = LCS[j];  
49.             }  
50.         }  
51.     }  
52.   
53.     delete LCS;  
54.     LCS = NULL;  
55.   
56.     return longestCommonSubString;  
57. }  
58.   
59. void Test(const char *testName, const char *pStr1, const char *pStr2, int expectedLongestCommonSubString)  
60. {  
61.     cout << testName << " : ";  
62.     if (GetLongestCommonSubString(pStr1, pStr2) == expectedLongestCommonSubString)  
63.     {  
64.         cout << "Passed." << endl;  
65.     }  
66.     else  
67.     {  
68.         cout << "Failed." << endl;  
69.     }  
70. }  
71.   
72. int main()  
73. {  
74.     Test("Test1", "caba", "bab", 2);  
75.     Test("Test2", "abcd", "efg", 0);  
76.     Test("Test3", "abcde", "abcde", 5);  
77. }  

(2)    找出两个字符串的最长公共子序列

题目：输入两个字符串，求两个字符串的最长公共子序列。

首先，最长公共子序列与最长公共子串不同，子序列不要求其在原字符串是连续的。例如字符串X={A,B,C,B,D,A,B}，Y = {B,D,C,A,B,A}，则X与Y的最长公共子序列为Z={B,C,B,A}。

我们假设X={x1, x2, x3, …, xm}，则X的前缀，Xi = {x1, x2, … ,xi}。即X={A,B,C,B,D,A,B}，X4={A,B,C,B}。

Y = {y1, y2, y3, … ,yn}，则Z={z1, z2, …,zk} 是X和Y的最长公共子序列。

如果xm == yn, 则zk = xm =yn 并且 Zk-1 是Xm-1 和 Yn-1的最长公共子序列。

如果 xm != yn, 则zk != xm，并且Z是Xm-1和Yn的最长公共子序列。

如果 xm != yn, 则zk != yn，并且Z是xm 和Yn-1的最长公共子序列。

所以我们定义了C[i][j]二维数组，用来存储Xi和Yj的最长公共子序列。

                            0                                  如果i==0或者j==0

即C[i][j] =           c[i-1][j-1] + 1               如果i,j > 0并且 xi == yj

                            Max(c[i][j-1],c[i-1][j])  如果i,j > 0 并且xi != yj

实现代码如下：

[cpp] view plain copy

1. #include <cstdio>  
2. #include <iostream>  
3. using namespace std;  
4.   
5. int max(int a, int b)  
6. {  
7.     return a > b ? a : b;  
8. }  
9.   
10. int GetLongestCommonSequence(const char *pStr1, const char *pStr2)  
11. {  
12.     /* 判断参数的合法性 */  
13.     if (pStr1 == NULL || pStr2 == NULL)  
14.     {  
15.         return -1;  
16.     }  
17.   
18.     int m = strlen(pStr1);  
19.     int n = strlen(pStr2);  
20.   
21.     /* 申请二维空间LCS[m+1][n+1] */  
22.     int **LCS = new int*[m+1];  
23.     for (int i = 0; i < m + 1; i++)  
24.     {  
25.         LCS[i] = new int[n+1];  
26.     }  
27.   
28.     /* 分别对LCS[i][0], LCS[0][j]赋值为0 */  
29.     for (int i = 0; i < m+1; i++)  
30.     {  
31.         LCS[i][0] = 0;  
32.     }  
33.     for (int j = 0; j < n+1; j++)  
34.     {  
35.         LCS[0][j] = 0;  
36.     }  
37.   
38.     /* 分别遍历两个字符串，并更新LCS[i][j] */  
39.     for (int i = 1; i < m+1; i++)  
40.     {  
41.         for (int j = 1; j < n+1; j++)  
42.         {  
43.             if (pStr1[i-1] == pStr2[j-1])  
44.             {  
45.                 LCS[i][j] = LCS[i-1][j-1] + 1;  
46.             }  
47.             else  
48.             {  
49.                 LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]);  
50.             }  
51.         }  
52.     }  
53.   
54.     /* 获取最长公共子序列 */  
55.     int longestCommonSequence = LCS[m][n];  
56.   
57.     /* 删除动态空间 */  
58.     for (int i = 0; i < m + 1; i++)  
59.     {  
60.         delete [] LCS[i];  
61.         LCS[i] = NULL;  
62.     }     
63.     delete []LCS;  
64.     LCS = NULL;  
65.   
66.     /* 返回最长公共子序列 */  
67.     return longestCommonSequence;  
68. }  
69.   
70. void Test(const char *testName, const char *pStr1, const char *pStr2, int expectedLongestCommonSequence)  
71. {  
72.     cout << testName << " : ";  
73.     if (GetLongestCommonSequence(pStr1, pStr2) == expectedLongestCommonSequence)  
74.     {  
75.         cout << "Passed." << endl;  
76.     }  
77.     else  
78.     {  
79.         cout << "Failed." << endl;  
80.     }  
81. }  
82.   
83. int main()  
84. {  
85.     Test("Test1", "ABCBDAB", "BDCABA", 4);  
86.     Test("Test2", "A", "A", 1);  
87.     Test("Test3", "AB", "BC", 1);  
88. }  

(3)    求两个字符串的编辑距离

问题：输入两个字符串，求它们的最短编辑距离。

我们定义了一套操作方法来把两个不同的字符串变得相同，具体的操作方法是：

1.      修改一个字符（如把“a”替换为“b”）

2.      增加一个字符（如把“abdd”变成“aebdd”）

3.      删除一个字符（如把“travelling”变成“traveling”）

我们每执行上述一个步骤，则它们之间的编辑距离加1.

 我们同样定义一个二维数组，C[i][j]表示字符串Xi和字符串Yi的最短编辑距离。

C[i][j] = min{C[i-1][j] + 1, C [i][j-1] + 1,C [i-1][j-1]+ 1(xi != yj), C[i-1][j-1](xi = yj)}。

实现代码如下：

[cpp] view plain copy

1. #include <cstring>  
2. #include <iostream>  
3. using namespace std;  
4.   
5. int min(int a, int b, int c)  
6. {  
7.     int min = a;  
8.     if (min > b)  
9.     {  
10.         min = b;  
11.     }  
12.     if (min > c)  
13.     {  
14.         min = c;  
15.     }  
16.     return min;  
17. }  
18.   
19. int GetLeastestEditDistance(const char *pStr1, const char *pStr2)  
20. {  
21.     if (pStr1 == NULL || pStr2 == NULL)  
22.     {  
23.         return -1;  
24.     }  
25.   
26.     int m = strlen(pStr1);  
27.     int n = strlen(pStr2);  
28.   
29.     /* 申请动态空间LED[m+1][n+1] */  
30.     int **LED = new int *[m+1];  
31.     for (int i = 0; i < m+1; i++)  
32.     {  
33.         LED[i] = new int[n+1];  
34.     }  
35.   
36.     /* 赋值LED[i][0] = i， LED[0][j] = j */  
37.     for (int i = 0; i < m+1; i++)  
38.     {  
39.         LED[i][0] = i;  
40.     }  
41.     for (int j = 0; j < n+1; j++)  
42.     {  
43.         LED[0][j] = j;  
44.     }  
45.   
46.     /* 计算LED[i][j] */  
47.     for (int i = 1; i < m+1; i++)  
48.     {  
49.         for (int j = 1; j < n+1; j++)  
50.         {  
51.             if (pStr1[i-1] == pStr2[j-1])  
52.             {  
53.                 LED[i][j] = min(LED[i-1][j-1], LED[i-1][j] + 1, LED[i][j-1] + 1);  
54.             }  
55.             else  
56.             {  
57.                 LED[i][j] = min(LED[i-1][j-1]+1, LED[i-1][j] + 1, LED[i][j-1] + 1);  
58.             }  
59.         }  
60.     }  
61.   
62.     /* 获得最小的编辑距离 */  
63.     int leastestEditDistance = LED[m][n];  
64.   
65.     /* 释放动态空间 */  
66.     for (int i = 0; i < m+1; i++)  
67.     {  
68.         delete [] LED[i];  
69.         LED[i] = NULL;  
70.     }  
71.     delete []LED;  
72.     LED = NULL;  
73.   
74.     /* 返回最小编辑距离 */  
75.     return leastestEditDistance;  
76. }  
77.   
78. void Test(const char *testName, const char *pStr1, const char *pStr2, int expectedLeastestEditDistance)  
79. {  
80.     cout << testName << " : ";  
81.     if (GetLeastestEditDistance(pStr1, pStr2) == expectedLeastestEditDistance)  
82.     {  
83.         cout << "Passed." << endl;  
84.     }  
85.     else  
86.     {  
87.         cout << "Failed." << endl;  
88.     }  
89. }  
90.   
91. int main()  
92. {  
93.     Test("Test1", "a", "b", 1);  
94.     Test("Test2", "abdd", "aebdd", 1);  
95.     Test("Test3", "travelling", "traveling", 1);  
96.     Test("Test4", "abcd", "abcd", 0);  
97.     Test("Test5", NULL, NULL, -1);  
98. }  

补充：

VS2013编写最长公共子串

// LongCS.cpp : 定义控制台应用程序的入口点。

//

#include "stdafx.h"

#include <cstring>  

#include <iostream>  

#include <algorithm>

using namespace std;

int GetLongestCommonSubString(const char *pStr1, const char *pStr2)

{

/* 判断参数合法性 */

if (pStr1 == NULL || pStr2 == NULL)

{

return -1;

}

int n = strlen(pStr1);

int m = strlen(pStr2);

int longestCommonSubString = 0;

/* 申请辅助空间，并初始化为0 */

int *LCS = new int[m];

for (int i = 0; i < m; i++)

{

LCS[i] = 0;

}

/* 不断判断pStr[i] ?= pStr[j]，然后根据不同情况来更新LCS */

for (int i = 0; i < n; i++)

{

for (int j = m - 1; j >= 0; j--)

{

if (pStr1[i] == pStr2[j])   /* 如果pStr1[i] == pStr2[j]，LCS[j] = LCS[j-1] + 1 */

{

if (j == 0)

{

LCS[j] = 1;

}

else

{

LCS[j] = LCS[j - 1] + 1;

}

}

else                        /* 如果pStr1[i] != pStr2[j]，LCS[j] = 0 */

{

LCS[j] = 0;

}

/* 更新最长子串的长度 */

if (LCS[j] > longestCommonSubString)

{

longestCommonSubString = LCS[j];

}

}

}

//打印出的不为0的数，就是最大子串

for (int i = 0; i < m; i++)

{

cout << LCS[i];

}

cout << endl;

delete LCS;

LCS = NULL;

return longestCommonSubString;

}

int _tmain(int argc, _TCHAR* argv[])

{

int res = GetLongestCommonSubString("abc","abcdef");

cout << res << endl;

system("pause");

return 0;

}