深入解析最長(zhǎng)公共子串
更新時(shí)間：2013年05月23日 18:14:51 作者：
本篇文章是對(duì)最長(zhǎng)公共子串進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下
題目：如果字符串一的所有字符按其在字符串中的順序出現(xiàn)在另外一個(gè)字符串二中，則字符串一稱之為字符串二的子串。注意，并不要求子串（字符串一）的字符必須連續(xù)出現(xiàn)在字符串二中。請(qǐng)編寫一個(gè)函數(shù)，輸入兩個(gè)字符串，求它們的最長(zhǎng)公共子串，并打印出最長(zhǎng)公共子串。
例如：輸入兩個(gè)字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它們的最長(zhǎng)公共子串，則輸出它們的長(zhǎng)度4，并打印任意一個(gè)子串。
分析：求最長(zhǎng)公共子串（Longest Common Subsequence, LCS）是一道非常經(jīng)典的動(dòng)態(tài)規(guī)劃題，因此一些重視算法的公司像MicroStrategy都把它當(dāng)作面試題。
完整介紹動(dòng)態(tài)規(guī)劃將需要很長(zhǎng)的篇幅，因此我不打算在此全面討論動(dòng)態(tài)規(guī)劃相關(guān)的概念，只集中對(duì)LCS直接相關(guān)內(nèi)容作討論。如果對(duì)動(dòng)態(tài)規(guī)劃不是很熟悉，請(qǐng)參考相關(guān)算法書比如算法討論。
考慮最長(zhǎng)公共子序列問(wèn)題如何分解成子問(wèn)題，設(shè)A=“a0，a1，…，am-1”，B=“b0，b1，…，bn-1”，并Z=“z0，z1，…，zk-1”為它們的最長(zhǎng)公共子序列。不難證明有以下性質(zhì)：
（1） 如果am-1==bn-1，則zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一個(gè)最長(zhǎng)公共子序列；
（2） 如果am-1!=bn-1，則若zk-1!=am-1時(shí)，蘊(yùn)涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一個(gè)最長(zhǎng)公共子序列；
（3） 如果am-1!=bn-1，則若zk-1!=bn-1時(shí)，蘊(yùn)涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一個(gè)最長(zhǎng)公共子序列。
這樣，在找A和B的公共子序列時(shí)，如果有am-1==bn-1，則進(jìn)一步解決一個(gè)子問(wèn)題，找“a0，a1，…，am-2”和“b0，b1，…，bm-2”的一個(gè)最長(zhǎng)公共子序列；如果am-1!=bn-1，則要解決兩個(gè)子問(wèn)題，找出“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一個(gè)最長(zhǎng)公共子序列和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一個(gè)最長(zhǎng)公共子序列，再取兩者中較長(zhǎng)者作為A和B的最長(zhǎng)公共子序列。
求解：
引進(jìn)一個(gè)二維數(shù)組c[][]，用c[i][j]記錄X[i]與Y[j] 的LCS 的長(zhǎng)度，b[i][j]記錄c[i][j]是通過(guò)哪一個(gè)子問(wèn)題的值求得的，以決定輸出最長(zhǎng)公共字串時(shí)搜索的方向。
我們是自底向上進(jìn)行遞推計(jì)算，那么在計(jì)算c[i,j]之前，c[i-1][j-1]，c[i-1][j]與c[i][j-1]均已計(jì)算出來(lái)。此時(shí)我們根據(jù)X[i] == Y[j]還是X[i] != Y[j]，就可以計(jì)算出c[i][j]。
問(wèn)題的遞歸式寫成：
由于每次調(diào)用至少向上或向左（或向上向左同時(shí)）移動(dòng)一步，故最多調(diào)用(m + n)次就會(huì)遇到i = 0或j = 0的情況，此時(shí)開始返回。返回時(shí)與遞歸調(diào)用時(shí)方向相反，步數(shù)相同，故算法時(shí)間復(fù)雜度為Θ(m + n)。
完整的實(shí)現(xiàn)代碼如下：
/**
找出兩個(gè)字符串的最長(zhǎng)公共子串的長(zhǎng)度
** author :liuzhiwei
** data :2011-08-15
**/
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int LCSLength(char* str1, char* str2, int **b)
{
int i,j,length1,length2,len;
length1 = strlen(str1);
length2 = strlen(str2);
//雙指針的方法申請(qǐng)動(dòng)態(tài)二維數(shù)組
int **c = new int*[length1+1]; //共有l(wèi)ength1+1行
for(i = 0; i < length1+1; i++)
c[i] = new int[length2+1]; //共有l(wèi)ength2+1列
for(i = 0; i < length1+1; i++)
c[i][0]=0; //第0列都初始化為0
for(j = 0; j < length2+1; j++)
c[0][j]=0; //第0行都初始化為0
for(i = 1; i < length1+1; i++)
{
for(j = 1; j < length2+1; j++)
{
if(str1[i-1]==str2[j-1]) //由于c[][]的0行0列沒(méi)有使用，c[][]的第i行元素對(duì)應(yīng)str1的第i-1個(gè)元素
{
c[i][j]=c[i-1][j-1]+1;
b[i][j]=0; //輸出公共子串時(shí)的搜索方向
}
else if(c[i-1][j]>c[i][j-1])
{
c[i][j]=c[i-1][j];
b[i][j]=1;
}
else
{
c[i][j]=c[i][j-1];
b[i][j]=-1;
}
}
}
/*
for(i= 0; i < length1+1; i++)
{
for(j = 0; j < length2+1; j++)
printf("%d ",c[i][j]);
printf("\n");
}
*/
len=c[length1][length2];
for(i = 0; i < length1+1; i++) //釋放動(dòng)態(tài)申請(qǐng)的二維數(shù)組
delete[] c[i];
delete[] c;
return len;
}
void PrintLCS(int **b, char *str1, int i, int j)
{
if(i==0 || j==0)
return ;
if(b[i][j]==0)
{
PrintLCS(b, str1, i-1, j-1); //從后面開始遞歸，所以要先遞歸到子串的前面，然后從前往后開始輸出子串
printf("%c",str1[i-1]); //c[][]的第i行元素對(duì)應(yīng)str1的第i-1個(gè)元素
}
else if(b[i][j]==1)
PrintLCS(b, str1, i-1, j);
else
PrintLCS(b, str1, i, j-1);
}
int main(void)
{
char str1[100],str2[100];
int i,length1,length2,len;
printf("請(qǐng)輸入第一個(gè)字符串：");
gets(str1);
printf("請(qǐng)輸入第二個(gè)字符串：");
gets(str2);
length1 = strlen(str1);
length2 = strlen(str2);
//雙指針的方法申請(qǐng)動(dòng)態(tài)二維數(shù)組
int **b = new int*[length1+1];
for(i= 0; i < length1+1; i++)
b[i] = new int[length2+1];
len=LCSLength(str1,str2,b);
printf("最長(zhǎng)公共子串的長(zhǎng)度為：%d\n",len);
printf("最長(zhǎng)公共子串為：");
PrintLCS(b,str1,length1,length2);
printf("\n");
for(i = 0; i < length1+1; i++) //釋放動(dòng)態(tài)申請(qǐng)的二維數(shù)組
delete[] b[i];
delete[] b;
system("pause");
return 0;
}
程序的效果圖如下：
第二種方法為：
/**
找出兩個(gè)字符串的最長(zhǎng)公共子串的長(zhǎng)度
** author :liuzhiwei
** data :2011-08-15
**/
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int LCSLength(char* str1, char* str2) //求得兩個(gè)字符串的最大公共子串長(zhǎng)度并輸出公共子串
{
int i,j,length1,length2;
length1 = strlen(str1);
length2 = strlen(str2);
//雙指針的方法申請(qǐng)動(dòng)態(tài)二維數(shù)組
int **c = new int*[length1+1]; //共有l(wèi)ength1+1行
for(i = 0; i < length1+1; i++)
c[i] = new int[length2+1]; //共有l(wèi)ength2+1列
for(i = 0; i < length1+1; i++)
c[i][0]=0; //第0列都初始化為0
for(j = 0; j < length2+1; j++)
c[0][j]=0; //第0行都初始化為0
for(i = 1; i < length1+1; i++)
{
for(j = 1; j < length2+1; j++)
{
if(str1[i-1]==str2[j-1]) //由于c[][]的0行0列沒(méi)有使用，c[][]的第i行元素對(duì)應(yīng)str1的第i-1個(gè)元素
c[i][j]=c[i-1][j-1]+1;
else if(c[i-1][j]>c[i][j-1])
c[i][j]=c[i-1][j];
else
c[i][j]=c[i][j-1];
}
}
//輸出公共子串
char s[100];
int len,k;
len=k=c[length1][length2];
s[k--]='\0';
i=length1,j=length2;
while(i>0 && j>0)
{
if(str1[i-1]==str2[j-1])
{
s[k--]=str1[i-1];
i--;
j--;
}
else if(c[i-1][j]<c[i][j-1])
j--;
else
i--;
}
printf("最長(zhǎng)公共子串為：");
puts(s);
for(i = 0; i < length1+1; i++) //釋放動(dòng)態(tài)申請(qǐng)的二維數(shù)組
delete[] c[i];
delete[] c;
return len;
}
int main(void)
{
char str1[100],str2[100];
int length1,length2,len;
printf("請(qǐng)輸入第一個(gè)字符串：");
gets(str1);
printf("請(qǐng)輸入第二個(gè)字符串：");
gets(str2);
length1 = strlen(str1);
length2 = strlen(str2);
len=LCSLength(str1,str2);
printf("最長(zhǎng)公共子串的長(zhǎng)度為：%d\n",len);
system("pause");
return 0;
}
問(wèn)題拓展：設(shè)A、B、C是三個(gè)長(zhǎng)為n的字符串，它們?nèi)∽酝怀?shù)大小的字母表。設(shè)計(jì)一個(gè)找出三個(gè)串的最長(zhǎng)公共子串的O(n^3)的時(shí)間算法。
思路：跟上面的求2個(gè)字符串的公共子串是一樣的思路，只不過(guò)這里需要?jiǎng)討B(tài)申請(qǐng)一個(gè)三維的數(shù)組，三個(gè)字符串的尾字符不同的時(shí)候，考慮的情況多一些而已。
/**
找出三個(gè)字符串的最長(zhǎng)公共子串的長(zhǎng)度
** author :liuzhiwei
** data :2011-08-15
**/
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int max1(int m,int n)
{
if(m>n)
return m;
else
return n;
}
int max2(int x,int y,int z,int k,int m,int n)
{
int max=-1;
if(x>max)
max=x;
if(y>max)
max=y;
if(z>max)
max=z;
if(k>max)
max=k;
if(m>max)
max=m;
if(n>max)
max=n;
return max;
}
int LCSLength(char* str1, char* str2, char* str3) //求得三個(gè)字符串的最大公共子串長(zhǎng)度并輸出公共子串
{
int i,j,k,length1,length2,length3,len;
length1 = strlen(str1);
length2 = strlen(str2);
length3 = strlen(str3);
//申請(qǐng)動(dòng)態(tài)三維數(shù)組
int ***c = new int**[length1+1]; //共有l(wèi)ength1+1行
for(i = 0; i < length1+1; i++)
{
c[i] = new int*[length2+1]; //共有l(wèi)ength2+1列
for(j = 0; j<length2+1; j++)
c[i][j] = new int[length3+1];
}
for(i = 0; i < length1+1; i++)
{
for(j = 0; j < length2+1; j++)
c[i][j][0]=0;
}
for(i = 0; i < length2+1; i++)
{
for(j = 0; j < length3+1; j++)
c[0][i][j]=0;
}
for(i = 0; i < length1+1; i++)
{
for(j = 0; j < length3+1; j++)
c[i][0][j]=0;
}
for(i = 1; i < length1+1; i++)
{
for(j = 1; j < length2+1; j++)
{
for(k = 1; k < length3+1; k++)
{
if(str1[i-1]==str2[j-1] && str2[j-1]==str3[k-1])
c[i][j][k]=c[i-1][j-1][k-1]+1;
else if(str1[i-1]==str2[j-1] && str1[i-1]!=str3[k-1])
c[i][j][k]=max1(c[i][j][k-1],c[i-1][j-1][k]);
else if(str1[i-1]==str3[k-1] && str1[i-1]!=str2[j-1])
c[i][j][k]=max1(c[i][j-1][k],c[i-1][j][k-1]);
else if(str2[j-1]==str3[k-1] && str1[i-1]!=str2[j-1])
c[i][j][k]=max1(c[i-1][j][k],c[i][j-1][k-1]);
else
{
c[i][j][k]=max2(c[i-1][j][k],c[i][j-1][k],c[i][j][k-1],c[i-1][j-1][k],c[i-1][j][k-1],c[i][j-1][k-1]);
}
}
}
}
len=c[length1][length2][length3];
for(i = 1; i < length1+1; i++) //釋放動(dòng)態(tài)申請(qǐng)的三維數(shù)組
{
for(j = 1; j < length2+1; j++)
delete[] c[i][j];
delete[] c[i];
}
delete[] c;
return len;
}
int main(void)
{
char str1[100],str2[100],str3[100];
int len;
printf("請(qǐng)輸入第一個(gè)字符串：");
gets(str1);
printf("請(qǐng)輸入第二個(gè)字符串：");
gets(str2);
printf("請(qǐng)輸入第三個(gè)字符串：");
gets(str3);
len=LCSLength(str1,str2,str3);
printf("最長(zhǎng)公共子串的長(zhǎng)度為：%d\n",len);
system("pause");
return 0;
}
程序的效果圖如下：
例如：輸入兩個(gè)字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它們的最長(zhǎng)公共子串，則輸出它們的長(zhǎng)度4，并打印任意一個(gè)子串。
分析：求最長(zhǎng)公共子串（Longest Common Subsequence, LCS）是一道非常經(jīng)典的動(dòng)態(tài)規(guī)劃題，因此一些重視算法的公司像MicroStrategy都把它當(dāng)作面試題。
完整介紹動(dòng)態(tài)規(guī)劃將需要很長(zhǎng)的篇幅，因此我不打算在此全面討論動(dòng)態(tài)規(guī)劃相關(guān)的概念，只集中對(duì)LCS直接相關(guān)內(nèi)容作討論。如果對(duì)動(dòng)態(tài)規(guī)劃不是很熟悉，請(qǐng)參考相關(guān)算法書比如算法討論。
考慮最長(zhǎng)公共子序列問(wèn)題如何分解成子問(wèn)題，設(shè)A=“a0，a1，…，am-1”，B=“b0，b1，…，bn-1”，并Z=“z0，z1，…，zk-1”為它們的最長(zhǎng)公共子序列。不難證明有以下性質(zhì)：
（1） 如果am-1==bn-1，則zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一個(gè)最長(zhǎng)公共子序列；
（2） 如果am-1!=bn-1，則若zk-1!=am-1時(shí)，蘊(yùn)涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一個(gè)最長(zhǎng)公共子序列；
（3） 如果am-1!=bn-1，則若zk-1!=bn-1時(shí)，蘊(yùn)涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一個(gè)最長(zhǎng)公共子序列。
這樣，在找A和B的公共子序列時(shí)，如果有am-1==bn-1，則進(jìn)一步解決一個(gè)子問(wèn)題，找“a0，a1，…，am-2”和“b0，b1，…，bm-2”的一個(gè)最長(zhǎng)公共子序列；如果am-1!=bn-1，則要解決兩個(gè)子問(wèn)題，找出“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一個(gè)最長(zhǎng)公共子序列和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一個(gè)最長(zhǎng)公共子序列，再取兩者中較長(zhǎng)者作為A和B的最長(zhǎng)公共子序列。
求解：
引進(jìn)一個(gè)二維數(shù)組c[][]，用c[i][j]記錄X[i]與Y[j] 的LCS 的長(zhǎng)度，b[i][j]記錄c[i][j]是通過(guò)哪一個(gè)子問(wèn)題的值求得的，以決定輸出最長(zhǎng)公共字串時(shí)搜索的方向。
我們是自底向上進(jìn)行遞推計(jì)算，那么在計(jì)算c[i,j]之前，c[i-1][j-1]，c[i-1][j]與c[i][j-1]均已計(jì)算出來(lái)。此時(shí)我們根據(jù)X[i] == Y[j]還是X[i] != Y[j]，就可以計(jì)算出c[i][j]。
問(wèn)題的遞歸式寫成：
回溯輸出最長(zhǎng)公共子序列過(guò)程：
由于每次調(diào)用至少向上或向左（或向上向左同時(shí)）移動(dòng)一步，故最多調(diào)用(m + n)次就會(huì)遇到i = 0或j = 0的情況，此時(shí)開始返回。返回時(shí)與遞歸調(diào)用時(shí)方向相反，步數(shù)相同，故算法時(shí)間復(fù)雜度為Θ(m + n)。
完整的實(shí)現(xiàn)代碼如下：
復(fù)制代碼 代碼如下:
/**
找出兩個(gè)字符串的最長(zhǎng)公共子串的長(zhǎng)度
** author :liuzhiwei
** data :2011-08-15
**/
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int LCSLength(char* str1, char* str2, int **b)
{
int i,j,length1,length2,len;
length1 = strlen(str1);
length2 = strlen(str2);
//雙指針的方法申請(qǐng)動(dòng)態(tài)二維數(shù)組
int **c = new int*[length1+1]; //共有l(wèi)ength1+1行
for(i = 0; i < length1+1; i++)
c[i] = new int[length2+1]; //共有l(wèi)ength2+1列
for(i = 0; i < length1+1; i++)
c[i][0]=0; //第0列都初始化為0
for(j = 0; j < length2+1; j++)
c[0][j]=0; //第0行都初始化為0
for(i = 1; i < length1+1; i++)
{
for(j = 1; j < length2+1; j++)
{
if(str1[i-1]==str2[j-1]) //由于c[][]的0行0列沒(méi)有使用，c[][]的第i行元素對(duì)應(yīng)str1的第i-1個(gè)元素
{
c[i][j]=c[i-1][j-1]+1;
b[i][j]=0; //輸出公共子串時(shí)的搜索方向
}
else if(c[i-1][j]>c[i][j-1])
{
c[i][j]=c[i-1][j];
b[i][j]=1;
}
else
{
c[i][j]=c[i][j-1];
b[i][j]=-1;
}
}
}
/*
for(i= 0; i < length1+1; i++)
{
for(j = 0; j < length2+1; j++)
printf("%d ",c[i][j]);
printf("\n");
}
*/
len=c[length1][length2];
for(i = 0; i < length1+1; i++) //釋放動(dòng)態(tài)申請(qǐng)的二維數(shù)組
delete[] c[i];
delete[] c;
return len;
}
void PrintLCS(int **b, char *str1, int i, int j)
{
if(i==0 || j==0)
return ;
if(b[i][j]==0)
{
PrintLCS(b, str1, i-1, j-1); //從后面開始遞歸，所以要先遞歸到子串的前面，然后從前往后開始輸出子串
printf("%c",str1[i-1]); //c[][]的第i行元素對(duì)應(yīng)str1的第i-1個(gè)元素
}
else if(b[i][j]==1)
PrintLCS(b, str1, i-1, j);
else
PrintLCS(b, str1, i, j-1);
}
int main(void)
{
char str1[100],str2[100];
int i,length1,length2,len;
printf("請(qǐng)輸入第一個(gè)字符串：");
gets(str1);
printf("請(qǐng)輸入第二個(gè)字符串：");
gets(str2);
length1 = strlen(str1);
length2 = strlen(str2);
//雙指針的方法申請(qǐng)動(dòng)態(tài)二維數(shù)組
int **b = new int*[length1+1];
for(i= 0; i < length1+1; i++)
b[i] = new int[length2+1];
len=LCSLength(str1,str2,b);
printf("最長(zhǎng)公共子串的長(zhǎng)度為：%d\n",len);
printf("最長(zhǎng)公共子串為：");
PrintLCS(b,str1,length1,length2);
printf("\n");
for(i = 0; i < length1+1; i++) //釋放動(dòng)態(tài)申請(qǐng)的二維數(shù)組
delete[] b[i];
delete[] b;
system("pause");
return 0;
}
程序的效果圖如下：
第二種方法為：
復(fù)制代碼 代碼如下:
/**
找出兩個(gè)字符串的最長(zhǎng)公共子串的長(zhǎng)度
** author :liuzhiwei
** data :2011-08-15
**/
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int LCSLength(char* str1, char* str2) //求得兩個(gè)字符串的最大公共子串長(zhǎng)度并輸出公共子串
{
int i,j,length1,length2;
length1 = strlen(str1);
length2 = strlen(str2);
//雙指針的方法申請(qǐng)動(dòng)態(tài)二維數(shù)組
int **c = new int*[length1+1]; //共有l(wèi)ength1+1行
for(i = 0; i < length1+1; i++)
c[i] = new int[length2+1]; //共有l(wèi)ength2+1列
for(i = 0; i < length1+1; i++)
c[i][0]=0; //第0列都初始化為0
for(j = 0; j < length2+1; j++)
c[0][j]=0; //第0行都初始化為0
for(i = 1; i < length1+1; i++)
{
for(j = 1; j < length2+1; j++)
{
if(str1[i-1]==str2[j-1]) //由于c[][]的0行0列沒(méi)有使用，c[][]的第i行元素對(duì)應(yīng)str1的第i-1個(gè)元素
c[i][j]=c[i-1][j-1]+1;
else if(c[i-1][j]>c[i][j-1])
c[i][j]=c[i-1][j];
else
c[i][j]=c[i][j-1];
}
}
//輸出公共子串
char s[100];
int len,k;
len=k=c[length1][length2];
s[k--]='\0';
i=length1,j=length2;
while(i>0 && j>0)
{
if(str1[i-1]==str2[j-1])
{
s[k--]=str1[i-1];
i--;
j--;
}
else if(c[i-1][j]<c[i][j-1])
j--;
else
i--;
}
printf("最長(zhǎng)公共子串為：");
puts(s);
for(i = 0; i < length1+1; i++) //釋放動(dòng)態(tài)申請(qǐng)的二維數(shù)組
delete[] c[i];
delete[] c;
return len;
}
int main(void)
{
char str1[100],str2[100];
int length1,length2,len;
printf("請(qǐng)輸入第一個(gè)字符串：");
gets(str1);
printf("請(qǐng)輸入第二個(gè)字符串：");
gets(str2);
length1 = strlen(str1);
length2 = strlen(str2);
len=LCSLength(str1,str2);
printf("最長(zhǎng)公共子串的長(zhǎng)度為：%d\n",len);
system("pause");
return 0;
}
問(wèn)題拓展：設(shè)A、B、C是三個(gè)長(zhǎng)為n的字符串，它們?nèi)∽酝怀?shù)大小的字母表。設(shè)計(jì)一個(gè)找出三個(gè)串的最長(zhǎng)公共子串的O(n^3)的時(shí)間算法。
思路：跟上面的求2個(gè)字符串的公共子串是一樣的思路，只不過(guò)這里需要?jiǎng)討B(tài)申請(qǐng)一個(gè)三維的數(shù)組，三個(gè)字符串的尾字符不同的時(shí)候，考慮的情況多一些而已。
復(fù)制代碼 代碼如下:
/**
找出三個(gè)字符串的最長(zhǎng)公共子串的長(zhǎng)度
** author :liuzhiwei
** data :2011-08-15
**/
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int max1(int m,int n)
{
if(m>n)
return m;
else
return n;
}
int max2(int x,int y,int z,int k,int m,int n)
{
int max=-1;
if(x>max)
max=x;
if(y>max)
max=y;
if(z>max)
max=z;
if(k>max)
max=k;
if(m>max)
max=m;
if(n>max)
max=n;
return max;
}
int LCSLength(char* str1, char* str2, char* str3) //求得三個(gè)字符串的最大公共子串長(zhǎng)度并輸出公共子串
{
int i,j,k,length1,length2,length3,len;
length1 = strlen(str1);
length2 = strlen(str2);
length3 = strlen(str3);
//申請(qǐng)動(dòng)態(tài)三維數(shù)組
int ***c = new int**[length1+1]; //共有l(wèi)ength1+1行
for(i = 0; i < length1+1; i++)
{
c[i] = new int*[length2+1]; //共有l(wèi)ength2+1列
for(j = 0; j<length2+1; j++)
c[i][j] = new int[length3+1];
}
for(i = 0; i < length1+1; i++)
{
for(j = 0; j < length2+1; j++)
c[i][j][0]=0;
}
for(i = 0; i < length2+1; i++)
{
for(j = 0; j < length3+1; j++)
c[0][i][j]=0;
}
for(i = 0; i < length1+1; i++)
{
for(j = 0; j < length3+1; j++)
c[i][0][j]=0;
}
for(i = 1; i < length1+1; i++)
{
for(j = 1; j < length2+1; j++)
{
for(k = 1; k < length3+1; k++)
{
if(str1[i-1]==str2[j-1] && str2[j-1]==str3[k-1])
c[i][j][k]=c[i-1][j-1][k-1]+1;
else if(str1[i-1]==str2[j-1] && str1[i-1]!=str3[k-1])
c[i][j][k]=max1(c[i][j][k-1],c[i-1][j-1][k]);
else if(str1[i-1]==str3[k-1] && str1[i-1]!=str2[j-1])
c[i][j][k]=max1(c[i][j-1][k],c[i-1][j][k-1]);
else if(str2[j-1]==str3[k-1] && str1[i-1]!=str2[j-1])
c[i][j][k]=max1(c[i-1][j][k],c[i][j-1][k-1]);
else
{
c[i][j][k]=max2(c[i-1][j][k],c[i][j-1][k],c[i][j][k-1],c[i-1][j-1][k],c[i-1][j][k-1],c[i][j-1][k-1]);
}
}
}
}
len=c[length1][length2][length3];
for(i = 1; i < length1+1; i++) //釋放動(dòng)態(tài)申請(qǐng)的三維數(shù)組
{
for(j = 1; j < length2+1; j++)
delete[] c[i][j];
delete[] c[i];
}
delete[] c;
return len;
}
int main(void)
{
char str1[100],str2[100],str3[100];
int len;
printf("請(qǐng)輸入第一個(gè)字符串：");
gets(str1);
printf("請(qǐng)輸入第二個(gè)字符串：");
gets(str2);
printf("請(qǐng)輸入第三個(gè)字符串：");
gets(str3);
len=LCSLength(str1,str2,str3);
printf("最長(zhǎng)公共子串的長(zhǎng)度為：%d\n",len);
system("pause");
return 0;
}
程序的效果圖如下：
您可能感興趣的文章:
- C語(yǔ)言求兩個(gè)字符串的最長(zhǎng)公共子串
- C++實(shí)現(xiàn)尋找最低公共父節(jié)點(diǎn)的方法
- JavaScript自定義函數(shù)實(shí)現(xiàn)查找兩個(gè)字符串最長(zhǎng)公共子串的方法
- Python最長(zhǎng)公共子串算法實(shí)例
- java實(shí)現(xiàn)求兩個(gè)字符串最長(zhǎng)公共子串的方法
- java實(shí)現(xiàn)字符串匹配求兩個(gè)字符串的最大公共子串
- Ruby實(shí)現(xiàn)的最長(zhǎng)公共子序列算法
- 利用C++實(shí)現(xiàn)最長(zhǎng)公共子序列與最長(zhǎng)公共子串
相關(guān)文章
Qt?timerEvent實(shí)現(xiàn)簡(jiǎn)單秒表功能
這篇文章主要為大家詳細(xì)介紹了Qt?timerEvent實(shí)現(xiàn)簡(jiǎn)單秒表功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-08-08
深入探索C++ string的底層實(shí)現(xiàn)
C語(yǔ)言中的字符串是以字符數(shù)組的形式存儲(chǔ)的,每個(gè)字符占用一個(gè)字節(jié)的內(nèi)存空間,本文我們將和大家一起深入探討一下string的底層實(shí)現(xiàn),感興趣的小伙伴快來(lái)和小編一起吧2023-08-08
C++實(shí)現(xiàn)類似延時(shí)停頓的打字效果
這篇文章主要介紹的是使用C++實(shí)現(xiàn)類似延時(shí)停頓的打字效果的代碼，非常的簡(jiǎn)單，推薦給大家，有需要的小伙伴可以參考下。2015-03-03
這篇文章主要介紹了C++設(shè)計(jì)模式之解釋器模式,本文講解了什么是解釋器模式、文法規(guī)則和抽象語(yǔ)法樹、解釋器模式的使用場(chǎng)合等內(nèi)容,需要的朋友可以參考下2014-10-10
這篇文章主要給大家介紹了關(guān)于C/C++混合編程之extern “C”使用的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧。2017-09-09
C++ 數(shù)據(jù)共享與保護(hù)的基本概念，包括標(biāo)識(shí)符的作用域與可見性，對(duì)象生存期，類數(shù)據(jù)的共享，類共享數(shù)據(jù)的保護(hù)。本篇文章就介紹C++ 數(shù)據(jù)共享與保護(hù),需要的朋友可以參考一下2021-10-10
C++ 中字符串操作--寬窄字符轉(zhuǎn)換的實(shí)例詳解
這篇文章主要介紹了C++ 中字符串操作--寬窄字符轉(zhuǎn)換的實(shí)例詳解的相關(guān)資料,希望通過(guò)本文能幫助到大家實(shí)現(xiàn)這樣的功能更，需要的朋友可以參考下2017-09-09
這篇文章主要介紹了C語(yǔ)言中函數(shù)指針的定義與使用,是C語(yǔ)言入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2016-04-04
這篇文章主要介紹了C++中的#,##,和"的相關(guān)知識(shí)，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友參考下吧2020-09-09
這篇文章主要為大家介紹了C++靜態(tài)成員函數(shù)和this指針，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2021-12-12