例如：输入两个字符串BDCABA 和ABCBDAB，字符串BCBA 和BDAB 都是是它们的最长公共子串，则
输出它们的长度4，并打印任意一个子串。
1.思路
注意最长子序列并不考虑连续性。对于序列str1,str2，设长度为m,n。建立辅助矩阵 c[m][n]，定义c[i][j]为子串str1[0-i]与子串str2[0-j]的最长子序列的长度，则c[m][n]的元素满足如下关系：
即假设求两字符串Xm ={x0, x1,…xm-1}和Yn={y0 ,y1,…,yn-1}的LCS，如果xm-1=yn-1，那么只需求得Xm-1 和Yn-1 的LCS，并在其后添加xm-1（yn-1）即可；如果xm-1≠yn-1，我们分别求得Xm-1 和Y 的LCS 和Yn-1 和X 的LCS，并且这两个LCS 中较长的一个为X 和Y 的LCS。
首先可以递归的求解。但是考虑到递归过程中的重复计算问题，此处使用辅助矩阵的方法。定义方向矩阵direction[m][n]. 由上叙，求取c[i,j]可能从c[i-1,j-1] 、c[i,j-1]或者c[i-1,j]三个方向计算得到，分别定义方向0，-1,1。
对direction矩阵反向遍历，当derection[i][j]==1时，str1[i]或str2[j]即为匹配字符之一。
2.代码
时间复杂度O(m*n)，空间复杂度为O(m,n)
#include<iostream>
#include<stack>
#include"string"
using namespace std;
//使用递归计算出子序列长度并输出子序列
bool getSubsequence(int **b,const string s,stack<char>& sub,int i,int j){
if(!b||(i*j)==0)
return false;
if(b[i][j]==0){
sub.push(s[j-1]);
getSubsequence(b,s,sub,i-1,j-1);//left-up
}
else if(b[i][j]==1)
getSubsequence(b,s,sub,i-1,j);//up
else
getSubsequence(b,s,sub,i,j-1);//left
return true;
}
bool LCSubsequence(const string str1, const string str2)
{
int length1,length2;
length1 = str1.size();
length2 = str2.size();
if(!length1||!length2)
return false;
int **c = new int*[length1+1];
int **direction=new int*[length1+1];//记录搜索方向
for(int i = 0; i < length1+1; i++){
c[i] = new int[length2+1];
c[i][0]=0; //第0列初始化为0
direction[i]=new int[length2+1];
}
for(int j = 0; j<length2+1; j++)
c[0][j]=0; //第0行初始化为0
//获得序列搜索路径存入direction
for(int i = 1; i < length1+1; i++)
{
for(int j = 1; j < length2+1; j++)
{
if(str1[i-1]==str2[j-1])
{
c[i][j]=c[i-1][j-1]+1;
direction[i][j]=0;
}
else if(c[i-1][j]>c[i][j-1])//1 means up
{
c[i][j]=c[i-1][j];
direction[i][j]=1;
}
else//-1 measns left
{
c[i][j]=c[i][j-1];
direction[i][j]=-1;
}
}
}
stack<char> sub;
//getSubsequence(direction,str2,sub,length1,length2);//使用递归计算出子序列长度并输出子序列
int i=length1,j=length2;
while(i*j!=0){
if(str1[i-1]==str2[j-1]){
sub.push(str1[i-1]);
i--;
j--;
}
else if(direction[i-1][j]>direction[i][j-1])
i--;
else
j--;
}
cout<<"length of LCS is "<< sub.size()<<endl;
cout<<"subsequence is----";
while(!sub.empty()){
cout<<sub.top()<<" ";
sub.pop();
}
cout<<endl;
//释放内存
for(int i = 0; i < length1+1; i++){
delete []c[i];
delete []direction[i] ;
}
delete []c;
delete []direction;
return true;
}
void main(){
const string s1("BDABA");
const string s2("ABMBCDATB");
LCSubsequence(s1,s2);
}
3.求最长公共子字符串
子字符串需要考虑字符连续问题。由于连续，故只有“左上”搜索方向，只需考虑如何计算c[i][j]即可。此时，若str1[i]==str2[j], c[i][j]=c[i-1][j-1]+1否则等于0。只需考虑最大的c[i][j]按斜对角线输出即可：
#include<iostream>
#include<stack>
#include"string"
using namespace std;
bool LCSubstring(const string str1, const string str2)
{
int length1,length2;
length1 = str1.size();
length2 = str2.size();
if(!length1||!length2)
return false;
int **c = new int*[length1+1];
for(int i = 0; i < length1+1; i++){
c[i] = new int[length2+1];
c[i][0]=0; //第0列初始化为0
}
for(int j = 0; j<length2+1; j++)
c[0][j]=0; //第0行初始化为0
int maxI=0;//当前最长公共子字符串的位置
int length=0;//最长公共子字符串的长度
for(int i = 1; i < length1+1; i++)
{
for(int j = 1; j < length2+1; j++)
{
if(str1[i-1]==str2[j-1])
c[i][j]=c[i-1][j-1]+1;
else
c[i][j]=0;
if(c[i][j]>length){
length=c[i][j];
maxI=i;
}
}
}
cout<<"最长公共子字符串为---";
for(int i=0;length&&i<length;i++)
cout<<str1[maxI-length+i];
cout<<endl;
//释放内存
for(int i = 0; i < length1+1; i++)
delete []c[i];
delete []c;
return true;
}
void main(){
const string s1("21232523311324");
const string s2("1523412321");
LCSubstring(s1,s2);
}
参考：