‘壹’ 动态规划 最长公共子串思想(c语言)
最长公共子串问题：一个给定序列的子序列是在该序列中删去若干元素后得到的序列。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。最长公共子串就是求给定两个序列的一个最长公共子序列。例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。
问题分析：
给定两个序列A和B，称序列Z是A和B的公共子序列，是指Z同是A和B的子序列。问题要求已知两序列A和B的最长公共子序列。如采用列举A的所有子序列，并一一检查其是否又是B的子序列，并随时记录所发现的子序列，最终求出最长公共子序列。这种方法因耗时太多而不可取。
考虑最长公共子序列问题如何分解成子问题，设A=“a0，a1，…，am-1”，B=“b0，b1，…，bm-1”，并Z=“z0，z1，…，zk-1”为它们的最长公共子序列。不难证明有以下性质：
（1） 如果am-1=bn-1，则zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一个最长公共子序列；
（2） 如果am-1!=bn-1，则若zk-1!=am-1，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列；
（3） 如果am-1!=bn-1，则若zk-1!=bn-1，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列。
这样，在找A和B的公共子序列时，如有am-1=bn-1，则进一步解决一个子问题，找“a0，a1，…，am-2”和“b0，b1，…，bm-2”的一个 最长公共子序列；如果am-1!=bn-1，则要解决两个子问题，找出“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列 和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列，再取两者中较长者作为A和B的最长公共子序列。
为了节约重复求相同子问题的时间，引入一个数组，不管它们是否对最终解有用，把所有子问题的解存于该数组中，这就是动态规划法所采用的基本方法，具体说明如下。
定义c[i][j]为序列“a0，a1，…，ai-2”和“b0，b1，…，bj-1”的最长公共子序列的长度，计算c[i][j]可递归地表述如下：
（1）c[i][j] = 0 如果i=0或j=0；
（2）c[i][j] = c[i-1][j-1]+1 如果i,j>0，且a[i-1] = b[j-1]；
（3）c[i][j] = max{c[i][j-1], c[i-1][j]} 如果i,j>0，且a[i-1] != b[j-1]。
按此算式可写出计算两个序列的最长公共子序列的长度函数。由于c[i][j]的产生仅依赖于c[i-1][j-1]、c[i-1][j]和c[i][j-1]，故可以从c[m][n]开始，跟踪c[i][j]的产生过程，逆向构造出最长公共子序列。
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/sharpdew/archive/2006/05/30/763180.aspx
‘贰’ C语言求最长子序列
下面是你的代码修改过后的结果，改过的地方都有注释，另有测试样例。
#include <stdio.h>
/*
5
5
-2 5 4 -7 3
最长子序列：9
4
-2 -3 8 -7
最长子序列：8
3
-2 -2 7
最长子序列：7
2
-1 5
最长子序列：5
1
-2
最长子序列：0
Process returned 0 (0x0) execution time : 30.999 s
Press any key to continue.
*/
int main() {
int count, i, k, a[100] = {0}, b[10000] = {0}, n, num, max = 0, q, m, j;
scanf("%d", &n);
for (count = 0; count < n; count++) {
scanf("%d", &num);
for (i = 0; i < num; i++) scanf("%d", &a[i]);
k = 0;
for (i = 0; i < num; i++)
for (q = 1; q < num + 1; q++) {
for (m = i; (m < i + q) && (m < num); m++) //在这里再加一个判断条件(m < num)，
b[k] += a[m];
k++;
}
j = k - 1;
max = 0; //如果全部都是负数的话，结果应该是0，即一个都不选
for (; j >= 0; j--)
if (max < b[j]) max = b[j];
printf("最长子序列：%d\n", max);
max = 0;
for (i = 0; i < 10000; i++) b[i] = 0;
}
return 0;
}
‘叁’ C语言 最长的连续的公共子序列
#include<stdio.h>
#define M 7
#define N 7
int c[M][N];
int b[M][N];
int lcsLength(char x[],char y[])
{
int m=M-1;
int n=N-1;
int i,j;
for(i=0;i<M;i++)
c[i][0]=0;
for(j=0;j<N;j++)
c[0][j]=0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
if(x[i]==x[j])
{
c[i][j]=c[i-1][j-1]+1;
b[i][j]=1;
}
else if(c[i-1][j]>=c[i][j-1])
{
c[i][j]=c[i-1][j];
b[i][j]=2;
}
else
{
c[i][j]=c[i][j-1];
b[i][j]=3;
}
}
return c[m][n];
}
void lcs(int i,int j,char x[],int b[M][N])
{
if(i==0||j==0)
return;
if(b[i][j]==1)
{
lcs(i-1,j-1,x,b);
printf("%-c,%d\t",x[i],i);
}
else if(b[i][j]==2)
lcs(i-1,j,x,b);
else
lcs(i,j-1,x,b);
}
void main()
{
char x[]={'0','A','B','C','B','D','A'};
char y[]={'0','B','H','C','A','B','A'};
int i,j;
printf("%d\n",lcsLength(x,y));
printf("\n");
lcs(M-1,N-1,x,b);
}
‘肆’ C语言 最长公共子串
首先指出楼主的错误
最长的公共子字符串 应该改成 最长的连续公共子字符串
下面是符合楼主要求的参考代码
//作者:hacker
//时间:9.12.2006
#include <stdio.h>
#include <string.h>
void main()
{
char* x="aabcdababce";
char* y="12abcabcdace";
int m = strlen(x);
int n = strlen(y);
int i, j, k, l;
int maxlength = 0;
int start = 0;
int count = 0;//用来判断是否匹配的变量
for (i=1;i<=n;i++)//匹配长度的循环
for (j=0;j<n-i+1;j++)//y的起始位置的循环
for (k=0;k<m-i+1;k++)//x的起始位置的循环
{
count = 0;
for (l=0;l<i;l++)//判断是否匹配,代码可以优化
if (y[j+l] == x[k+l])
count++;
if (count==i&&i>maxlength)
{
maxlength = i;//记录最大长度
start = j;//记录最大长度的起起位置
}
}
//作者:hacker
//时间:9.12.2006
#include <stdio.h>
#include <string.h>
void main()
{
char* x="aabcdababce";
char* y="12abcabcdace";
int m = strlen(x);
int n = strlen(y);
int i, j, k, l;
int maxlength = 0;
int start = 0;
int count = 0;//用来判断是否匹配的变量
for (i=1;i<=n;i++)//匹配长度的循环
for (j=0;j<n-i;j++)//y的起始位置的循环
for (k=0;k<m-i;k++)//x的起始位置的循环
{
count = 0;
for (l=0;l<i;l++)//判断是否匹配,代码可以优化
if (y[j+l] == x[k+l])
count++;
if (count==i&&i>maxlength)
{
maxlength = i;//记录最大长度
start = j;//记录最大长度的起起位置
}
}
if (maxlength==0)
printf("No Answer");
else
for (i=0;i<maxlength;i++)
printf("%c",y[start+i]);
}
}
下面是真正的最长公共子串的动态规划算法
//作者:hacker
//时间:9.12.2006
#include <stdio.h>
#include <string.h>
int b[50][50];
int c[50][50];
void lcs(x,m,y,n)
char *x;
int m;
char *y;
int n;
{
int i;
int j;
for (i=1;i<=m;i++) c[i][0] = 0;
for (i=1;i<=n;i++) c[0][i] = 0;
c[0][0] = 0;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
{
if (x[i-1] == y[j-1])
{
c[i][j] = c[i-1][j-1] + 1;
b[i][j] = 1;
}
else
if (c[i-1][j] > c[i][j-1])
{
c[i][j] = c[i-1][j];
b[i][j] = 2;
}
else
{
c[i][j] = c[i][j-1];
b[i][j] = 3;
}
}
}
void show(i,j,x)
int i;
int j;
char* x;
{
if (i==0||j==0)
return;
if (b[i][j]==1)
{
show(i-1,j-1,x);
printf("%c",x[i-1]);
}
else
if (b[i][j]==2)
show(i-1,j,x);
else
show(i,j-1,x);
}
void main()
{
char* x="aabcdababce";
char* y="12abcabcdace";
int m = strlen(x);
int n = strlen(y);
lcs(x,m,y,n);
show(m,n,x);
}
‘伍’ C语言LCIS（最长公共上升子序列）（DP）如何打印解
用一个解向量存储解啊，思路如下
function(..., char v[]) /*v用于存储最优解的*/
{
......
if(当前解更优){
当前解为更优解;
更新向量v; /*最好附添加一个结束符*/
}
......
}
主函数中输出解向量即可。
‘陆’ 求问c语言最长公共子序列代码哪里错了！！！ 搞了好久，头晕了都。 感觉是对的，就是不行。。。
楼主你好。
#include<stdio.h>
void LCSLength(int m,int n,char *x,char *y,int c[8][7],int b[8][7])
{
int i,j;
//下面两行不怎么需要，因为已经初始化为0了
for(i=0;i<m;i++) c[i][0]=0;//注意应该是从0到m-1
for(i=0;i<n;i++) c[0][i]=0;
for(i=1;i<m;i++){//这里注意应该是从1到m-1
for(j=1;j<n;j++){
if(x[i]==y[j]){
c[i][j]=c[i-1][j-1]+1;
b[i][j]=1;
}else if(c[i-1][j]>=c[i][j-1]){
c[i][j]=c[i-1][j];
b[i][j]=2;
}else {
c[i][j]=c[i][j-1];
b[i][j]=3;
}
}
}
}
void printMatrix(int matrix[8][7]){
int i,j;
for(i=0;i<8;i++){
for(j=0;j<7;j++){
printf("%d ",matrix[i][j]);
}
printf("\n");
}
}
void LCS(int i,int j,char *x,int b[8][7] )
{
if(i==0||j==0) return;
if(b[i][j]==1){
LCS(i-1,j-1,x,b);
printf("%c\n",x[i]);
}else if(b[i][j]==2){//这里注意是==，不是=
LCS(i-1,j,x,b);
}else{
LCS(i,j-1,x,b);
}
}
int main()
{
int c[8][7]={{0}};
int b[8][7]={{0}};
char X[8]={' ','A','B','C','B','D','A','B'};
char Y[7]={' ','B','D','C','A','B','A'};
LCSLength(8,7,X,Y,c,b);
printf("Matrix c\n");
printMatrix(c);
printf("Matrix b\n");
printMatrix(b);
printf("最大公共子序列长度为%d\n",c[7][6]);
LCS(7,6,X,b);
return 1;
}
你运行一下我的代码，没问题的。代码中出现的问题我以注释的形式写出来了。
不过劝告楼主，以后写代码一定要多写一些注释。因为一般的程序员都能写出机器能读懂的代码，而高级程序员才能写出人也能读懂的代码。写注释很重要，显示出代码的思路。否则思路不清晰的高深代码，一开始只有原作者和上帝能懂，过一段时间就只有上帝能懂了。
如果还有问题可以再问。
‘柒’ 求最长公共子序列的c语言代码
？？？
‘捌’ C语言求两字符序列的最长公共字符子序列，这个代码哪错了
大哥，刚开始看我以为你是个新手，仔细看，回调都敢用...
问题太多了， main函数里定义函数...
知道往函数里传递两个字符串长度，怎么不把两个字符串传里？
然后返回值是int 却想返回个二维数组..传值麻烦干脆全定义成全局变量多好 还有就是递归能不用就最好不用，一般递归都可以用 循环代替，递归太占栈
‘玖’ 求一个最长公共自序列的程序，C语言的，拜托了
#include<stdio.h>
void LCSLength(int m,int n,char *x,char *y,int c[8][7],int b[8][7])
{
int i,j;
for(i=0;i<m;i++) c[i][0]=0;
for(i=0;i<n;i++) c[0][i]=0;
for(i=1;i<m;i++){
for(j=1;j<n;j++){
if(x[i]==y[j]){
c[i][j]=c[i-1][j-1]+1;
b[i][j]=1;
}else if(c[i-1][j]>=c[i][j-1]){
c[i][j]=c[i-1][j];
b[i][j]=2;
}else {
c[i][j]=c[i][j-1];
b[i][j]=3;
}
}
}
}
void printMatrix(int matrix[8][7]){
int i,j;
for(i=0;i<8;i++){
for(j=0;j<7;j++){
printf("%d ",matrix[i][j]);
}
printf("\n");
}
}
void LCS(int i,int j,char *x,int b[8][7] )
{
if(i==0||j==0) return;
if(b[i][j]==1){
LCS(i-1,j-1,x,b);
printf("%c\n",x[i]);
}else if(b[i][j]==2){
LCS(i-1,j,x,b);
}else{
LCS(i,j-1,x,b);
}
}
int main()
{
int c[8][7]={{0}};
int b[8][7]={{0}};
char X[8]={' ','A','B','C','B','D','A','B'};
char Y[7]={' ','B','D','C','A','B','A'};
LCSLength(8,7,X,Y,c,b);
printf("Matrix c\n");
printMatrix(c);
printf("Matrix b\n");
printMatrix(b);
printf("最大公共子序列长度为%d\n",c[7][6]);
LCS(7,6,X,b);
return 1;
}