下面的程序分別實現了使用LCS求連續子串和不連續子串的匹配情況！
//查找兩個字符串中的最長公共子串
//例如：abcdef 和 bdf 最長公共子串長度是3
//f(n,m)=f(n-1,m-1)+1 如果兩個字符串的第一個字母相等
// =max(f(n-1,m),f(n,m-1)) 如果兩個字符串的第一個字母不相等
//遞歸最後的條件是f(n,0)=f(0,m)=0
//不要求匹配的子串是連續的子串
#include<iostream>
#include<cstring>
#include<stdlib.h>
using namespace std;
int main()
{
char stra[20],strb[20];
cin>>stra>>strb;
int lengtha=strlen(stra);
int lengthb=strlen(strb);
int lcs_len(char *stra,int bega,int enda,char *strb,int begb,int endb); //使用數組下表來代表n和m
cout<<lcs_len(stra,0,lengtha-1,strb,0,lengthb-1)<<endl;
system("pause");
return 0;
}
int lcs_len(char *stra,int bega,int enda,char *strb,int begb,int endb)
{
if(bega>enda||begb>endb) //此處的條件不可寫成bega>=enda||begb>=endb
return 0;
if(stra[bega]==strb[begb])
return lcs_len(stra,bega+1,enda,strb,begb+1,endb)+1;
else
{
if((lcs_len(stra,bega,enda,strb,begb+1,endb))>(lcs_len(stra,bega+1,enda,strb,begb,endb)))
return lcs_len(stra,bega,enda,strb,begb+1,endb);
else
return lcs_len(stra,bega+1,enda,strb,begb,endb);
}
}//非遞歸算法
//矩陣運算，if(a[i]==b[j])
// c[i][j]=c[i-1][j-1]+1; 左上角的值+1
// else
// c[i][j]=((c[i-1][j]>c[i][j-1])?c[i-1][j]:c[i][j-1]); 上下的最大值
#include<iostream>
#include<cstring>
using namespace std;
#define M 1000
char c[M][M];
char a[M];
char b[M];
int my_lcs(char a[],char b[]){
int i,j;
int m=strlen(a);
int n=strlen(b);
for(i=0;i<m;++i){
for(j=0;j<n;++j){
if(a[i]==b[j])
c[i][j]=c[i-1][j-1]+1;
else
c[i][j]=((c[i-1][j]>c[i][j-1])?c[i-1][j]:c[i][j-1]);
}
}
int maxnum=-32768;
for(i=0;i<m;++i)
for(j=0;j<n;++j)
if(c[i][j]>maxnum)
maxnum=c[i][j];
return maxnum;
}
int main(){
cin>>a>>b;
cout<<my_lcs(a,b)<<endl;
return 0;
}
//匹配的子串是連續的子串
//非遞歸方法
/*
解法就是用一個矩陣來記錄兩個字符串中所有位置的兩個字符之間的匹配情況，若是匹配則為1，否則為0。
然後求出對角線最長的1序列，其對應的位置就是最長匹配子串的位置.
下面是字符串21232523311324和字符串312123223445的匹配矩陣，前者為X方向的，後者為Y方向的。
不難找到，紅色部分是最長的匹配子串。通過查找位置我們得到最長的匹配子串為：21232
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
但是在0和1的矩陣中找最長的1對角線序列又要花去一定的時間。通過改進矩陣的生成方式和設置標記變量，
可以省去這部分時間。下面是新的矩陣生成方式：
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
0 1 0 0 0 0 0 0 0 2 1 0 0 0 0
1 0 2 0 1 0 1 0 0 0 0 0 1 0 0
0 2 0 0 0 0 0 0 0 1 1 0 0 0 0
1 0 3 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 4 0 0 0 2 1 0 0 1 0 0 0
1 0 1 0 5 0 1 0 0 0 0 0 2 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 2 0 0 0 2 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
當字符匹配的時候，我們並不是簡單的給相應元素賦上1，而是賦上其左上角元素的值加一。
我們用兩個標記變量來標記矩陣中值最大的元素的位置，在矩陣生成的過程中來判斷當前生成的元素的值是不是最大的，
據此來改變標記變量的值，那麼到矩陣完成的時候，最長匹配子串的位置和長度就已經出來了。
*/
#include<iostream>
using namespace std;
#define N 1000
char str[N][N];
int main(){
string s1,s2;
cin>>s1>>s2;
int len1=s1.size();
int len2=s2.size();
int i,j;
for(i=0;i<len1;++i){
for(j=0;j<len2;++j){
if(j==0){
if(s1[i]==s2[j])
str[j][i]=1;
else
str[j][i]=0;
}
else{
if(s1[i]==s2[j])
str[j][i]=str[j-1][i-1]+1;
else
str[j][i]=0;
}
}
}
int max=-32768;
for(i=0;i<len1;++i){
for(j=0;j<len2;++j){
if(str[i][j]>max)
max=str[i][j];
}
}
cout<<max<<endl;
return 0;
}本文出自 “菜鳥的進階之路” 博客，請務必保留此出處http://beyond316.blog.51cto.com/7367775/1266360
