最长公共子序列和最长公共子串(C语言实现)c/c++qq42453280的博客-

核心思想：
利用动态规划的思想，通过设置一个临时数组t[][]，其中t[i][j]表示，以Str1[i]作为末尾和以Str[2]作为末尾的最长公共子序列或者子串的长度。

算法步骤：
（1）将输入的两个字符串分别存在数组a[]和b[]中，同时设置两个临时数组t1[][]和t2[][]，第一个t1[i][j]表示a[]数组前i-1个字符串和b[]数组前j-1个字符串的最大公共子序列；第二个t2[i][j]表示a[]数组前i-1个字符串和b[]数组前j-1个字符串的最大公共子串；
（2）循坏遍历两个字符串的所有字符，当遍历到第一个字符串的第i个字符，第二个字符串的第j个字符时：
对于最长公共子序列:
若a[i]=b[j]，则t1[i][j]=t1[i-1][j-1]+1;
若a[i]!=b[j]，则t1[i][j]=Max{a[k][j],(-1<k<i)，a[i][m](-1<k<j)}
对于最长公共子串：
若a[i]=b[j]，则t2[i][j]=t2[i-1][j-1]+1;
若a[i]!=b[j]，则t2[i][j]=0。
（3）t1[][]数组最右下角的便是最长公共子序列的长度；而t2[][]数组中最大的元素才是最长公共子串的长度。

注意：
子序列：从字符串中顺序地取出字符组成的字符串；
子串：从字符串中连续地取出字符组成的字符串。

实例以及代码

//定义全局变量 int t1[20][20]={0},t2[20][20]={0}; char a[20],l1=1,b[20],l2=1; 

//存储输入，初始化临时二维数组 void Input(){ char ch; printf("请输入两个字符串:");  ch=getchar(); while(ch!=' ') {   a[l1++]=ch;   ch=getchar(); }  ch=getchar(); while(ch!='n') {   b[l2++]=ch;   ch=getchar(); } } 

//对于a[i]是否等于b[j]的处理 void LCDSubsequence(){ //最长公共子序列 int i,j,max,k; for(i=1;i<l1;i++) for(j=1;j<l2;j++) { if(a[i]==b[j])     t1[i][j]=t1[i-1][j-1]+1; else {     max=0; for(k=0;k<i;k++) if(t1[k][j]>max)       max=t1[k][j]; for(k=0;k<j;k++) if(t1[i][k]>max)       max=t1[i][k];        t1[i][j]=max; } } } 

//对于a[i]是否等于b[j]的处理 void LCCSubsequence(){ //最长公共子串 int i,j; for(i=1;i<l1;i++) for(j=1;j<l2;j++) { if(a[i]==b[j])     t2[i][j]=t2[i-1][j-1]+1; else {     t2[i][j]=0; } } } 

//分别输出 void Output(){ printf("最长公共子序列为:"); printf("%dn",t1[l1-1][l2-1]); int i,j,max=0; printf("最长公共连续序列为:"); for(i=1;i<l1;i++) for(j=1;j<l2;j++) if(t2[i][j]>max)     max=t2[i][j]; printf("%d",max); } 

int main(){ Input(); LCDSubsequence(); LCCSubsequence(); Output(); return 0; } 

运行结果：