一区二区三区日韩精品-日韩经典一区二区三区-五月激情综合丁香婷婷-欧美精品中文字幕专区

搜索
分享

C++ 筆試之基礎(chǔ) 08 求兩個(gè)字符串的最長公共子串，最長公共子序列，編輯距離

 雪柳花明 2017-02-17

(1)    找出兩個(gè)字符串的最長公共子串

題目：輸入兩個(gè)字符串，找出兩個(gè)字符串中最長的公共子串。

找兩個(gè)字符串的最長公共子串，這個(gè)子串要求在原字符串中是連續(xù)的。因此我們采用一個(gè)二維矩陣來存儲(chǔ)中間結(jié)果，下面我們看這個(gè)二維數(shù)組如何構(gòu)造？

假設(shè)兩個(gè)字符串分別是：”bab”和”caba”。


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

然后我們從矩陣中找出斜對(duì)角線最長的那個(gè)子字符串，就是最長公共子串。

即”ab”和”ba”分別為2。

我們可以簡化一下，在當(dāng)我們計(jì)算matrix[i][j]時(shí)，我們判斷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。

如下圖所示：


所以此時(shí)，我們只是將matrix[M][N]中，找到最大的值，即為最長公共子串。

然后我們還可以簡化一下空間復(fù)雜度。

因?yàn)槲覀兠颗袛嘁粋€(gè)matrix[i][j]時(shí)，實(shí)際上它只與matrix[i-1][j-1]相關(guān)。故所以我們可以使用一維數(shù)組來保存上一次的結(jié)果。

實(shí)現(xiàn)代碼如下：

  1. #include <cstring>  
  2. #include <iostream>  
  3. using namespace std;  
  4.   
  5. int GetLongestCommonSubString(const char *pStr1, const char *pStr2)  
  6. {  
  7.     /* 判斷參數(shù)合法性 */  
  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.     /* 申請(qǐng)輔助空間，并初始化為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]，然后根據(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)    找出兩個(gè)字符串的最長公共子序列

題目：輸入兩個(gè)字符串，求兩個(gè)字符串的最長公共子序列。

首先，最長公共子序列與最長公共子串不同，子序列不要求其在原字符串是連續(xù)的。例如字符串X={A,B,C,B,D,A,B}，Y = {B,D,C,A,B,A}，則X與Y的最長公共子序列為Z={B,C,B,A}。

我們假設(shè)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]二維數(shù)組，用來存儲(chǔ)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

實(shí)現(xiàn)代碼如下：

  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.     /* 判斷參數(shù)的合法性 */  
  13.     if (pStr1 == NULL || pStr2 == NULL)  
  14.     {  
  15.         return -1;  
  16.     }  
  17.   
  18.     int m = strlen(pStr1);  
  19.     int n = strlen(pStr2);  
  20.   
  21.     /* 申請(qǐng)二維空間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.     /* 分別對(duì)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.     /* 分別遍歷兩個(gè)字符串，并更新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.     /* 刪除動(dòng)態(tài)空間 */  
  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)    求兩個(gè)字符串的編輯距離

問題：輸入兩個(gè)字符串，求它們的最短編輯距離。

我們定義了一套操作方法來把兩個(gè)不同的字符串變得相同，具體的操作方法是：

1.      修改一個(gè)字符（如把“a”替換為“b”）

2.      增加一個(gè)字符（如把“abdd”變成“aebdd”）

3.      刪除一個(gè)字符（如把“travelling”變成“traveling”）

我們每執(zhí)行上述一個(gè)步驟，則它們之間的編輯距離加1.

 我們同樣定義一個(gè)二維數(shù)組，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)}。

實(shí)現(xiàn)代碼如下：

  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.     /* 申請(qǐng)動(dòng)態(tài)空間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.     /* 計(jì)算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.     /* 釋放動(dòng)態(tài)空間 */  
  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. }  

補(bǔ)充：
VS2013編寫最長公共子串
// LongCS.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。
//

#include "stdafx.h"
#include <cstring>  
#include <iostream>  
#include <algorithm>

using namespace std;

int GetLongestCommonSubString(const char *pStr1, const char *pStr2)
{
/* 判斷參數(shù)合法性 */
if (pStr1 == NULL || pStr2 == NULL)
{
return -1;
}
int n = strlen(pStr1);
int m = strlen(pStr2);
int longestCommonSubString = 0;
/* 申請(qǐng)輔助空間，并初始化為0 */
int *LCS = new int[m];
for (int i = 0; i < m; i++)
{
LCS[i] = 0;
}

/* 不斷判斷pStr[i] ?= pStr[j]，然后根據(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的數(shù)，就是最大子串
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;
}

    本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。
    轉(zhuǎn)藏 分享 獻(xiàn)花（0）

    0條評(píng)論

    發(fā)表

    請(qǐng)遵守用戶 評(píng)論公約

    類似文章 更多

    国产91麻豆精品成人区| 亚洲男人天堂成人在线视频| 亚洲人午夜精品射精日韩| 亚洲免费黄色高清在线观看 | 中国黄色色片色哟哟哟哟哟哟| 国产丝袜女优一区二区三区| 国产午夜在线精品视频| 亚洲欧美日韩精品永久| 又大又长又粗又猛国产精品| 国产日产欧美精品大秀| 日韩一区欧美二区国产| 中文字幕日韩欧美一区| 亚洲国产成人久久一区二区三区 | 国产一二三区不卡视频| 东京热加勒比一区二区| 精品香蕉一区二区在线| 欧美久久一区二区精品| 国产精品99一区二区三区| 免费大片黄在线观看日本| 亚洲国产av精品一区二区| 日木乱偷人妻中文字幕在线| 激情三级在线观看视频| 欧美乱码精品一区二区三| 一个人的久久精彩视频| 天堂热东京热男人天堂| 国产日韩熟女中文字幕| 成人精品网一区二区三区| 欧美日韩精品一区免费| 一区二区三区人妻在线| 中文字幕一区久久综合| 国产欧美日韩综合精品二区| 91一区国产中文字幕| 国产不卡视频一区在线| 欧美老太太性生活大片| 91精品国产av一区二区| 国产老熟女乱子人伦视频| 亚洲午夜精品视频在线| 一区二区三区亚洲天堂| 久久99亚洲小姐精品综合| 亚洲中文字幕在线综合视频| 激情亚洲一区国产精品久久|