求最长子序列,怎么输入都是输出最短的那个,或是一个拼接答案,该怎么改?
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define MAX 64
typedef struct node{
char data[MAX];
int length;
}SqString;
void StrAssign(SqString *s,char cstr[])
{
int i;
for (i=0;cstr[i]!='\0';i++)
s->data[i]=cstr[i];
s->data[i]='\0';
s->length=i;
}
SqString* SubStr(SqString *s,int i,int j)
{
SqString* str;
int k;
str->length=0;
if (i<0 || i>s->length || j<0 || i+j-1>s->length)
return str; //参数不正确时返回空串
for (k=i;k<i+j-1;k++) //s->data[i..i+j]?str
str->data[k-i]=s->data[k];
str->length=j-1;
return str;
}
bool SubContains(SqString* s1,SqString* temp)
{
int i = 0, j = 0, flag = -1;
while (i < s1->length && j < temp->length)
{
if (s1->data[i] == temp->data[j])
{
i++;
j++;
}
else
{
i = i - j + 1; //主串字符回到比较最开始比较的后一个字符
j = 0; //字串字符重新开始
}
if (j == temp->length)
{ //如果匹配成功
flag = 1; //字串出现
break;
}
}
return flag;
}
SqString* MaxSubstring(SqString* s1,SqString* s2){
SqString* max,*min;
max=(s1->length>s2->length)?s1:s2;
min=(max==s1)?s2:s1;
for(int i=0;i<min->length;i++)
{
for(int j=0,k=min->length-i;k!=min->length+1;j++,k++)
{
SqString* temp=SubStr(min,j,k-j-1);
if(SubContains(max,temp))
return temp;
}
}
return 0;
}
int main(){
char a1[100],a2[100];
SqString* s,s1,s2;
printf("请输入第一个字符串:");
gets(a1);
printf("请输入第二个字符串:");
gets(a2);
StrAssign(&s1,a1);
StrAssign(&s2,a2);
s=MaxSubstring(&s1,&s2);
printf("%s",s->data);
return 0;
}
//最大公共子序列的问题
#include <stdio.h>
#include <string.h>
#define MAXSIZE 200
int c[200][200];
int b[200][200];
char f[200];
void print(int i, int j, int s, char x[], char y[]);
int max(int m, int n, int i, int j) // c[i][j-1].c[i-1][j]
{
if (m > n) {
b[i][j] = 1;
return m;
} else {
b[i][j] = -1;
return n;
}
}
int LCS(char x[], char y[]) {
int i, j;
int m, n;
m = strlen(x);
n = strlen(y);
for (i = 0; i < m + 1; i++)
c[i][0] = 0;
for (j = 0; j < n + 1; j++)
c[0][j] = 0;
for (i = 1; i <= m; i++) {
for (j = 1; j <= n; j++) {
if (x[i - 1] == y[j - 1]) {
b[i][j] = 0;
c[i][j] = c[i - 1][j - 1] + 1;
} else {
c[i][j] = max(c[i][j - 1], c[i - 1][j], i, j);
}
}
}
printf("X和Y的LCS是:");
print(m, n, c[m][n], x, y);
printf("%s\n", f);
return c[i - 1][j - 1];
}
void print(int i, int j, int s, char x[], char y[]) {
if (b[i][j] == 0) {
f[s - 1] = x[i - 1];
i--;
j--;
s--;
print(i, j, s, x, y);
} else if (b[i][j] == 1) {
j--;
print(i, j, s, x, y);
} else if (b[i][j] == 1) {
i--;
print(i, j, s, x, y);
}
}
int main() {
char x[MAXSIZE];
char y[MAXSIZE];
printf("你要输入的X字符串为:");
scanf("%s", x);
printf("你要输入的Y字符串为:");
scanf("%s", y);
int s = LCS(x, y);
printf("公共子序列长度为:%d\n", s);
return 0;
}