#include <stdio.h>
#include <string.h>
int b[50][50];
int c[50][50];
int length = 0;
void lcs(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;
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(int i, int j, char *x)
{
if(i == 0 || j ==0)
return;
if(b[i][j] == 1)
{
show(i-1, j-1, x);
length++;
printf("%c", x[i-1]);
}
else if(b[i][j] == 2)
{
show(i-1, j, x);
}
else
{
show(i, j-1, x);
}
}
int main()
{
char *x = "xyzrfdt";
char *y = "xzhrgfiut"; //xzrft
int m = strlen(x);
int n = strlen(y);
lcs(x,m,y,n);
printf("The string is: \n");
show(m, n, x);
}
1 #include <iostream>
2 #include <
string>
3 using namespace std;
4 int main(
int argc,
char **
argv)
5 {
6 string str1 =
"ABCBDAB";
7 string str2 =
"BDCABA";
8
9 int x_len =
str1.length();
10 int y_len =
str2.length();
11
12 int arr[
50][
50] = {{
0,
0}};
13
14 int i =
0;
15 int j =
0;
16
17 for(i =
1; i <= x_len; i++
)
18 {
19 for(j =
1; j <= y_len; j++
)
20 {
21 if(str1[i -
1] == str2[j -
1])
22 {
23 arr[i][j] = arr[i -
1][j -
1] +
1;
24 }
25 else
26 {
27
28 if(arr[i][j -
1] >= arr[i -
1][j])
29 {
30 arr[i][j] = arr[i][j -
1];
31 }
32 else
33 {
34 arr[i][j] = arr[i -
1][j];
35 }
36 }
37
38 }
39 }
40 for(i =
0 ; i <= x_len; i++
)
41 {
42 for( j =
0; j <= y_len; j++
)
43 {
44 cout << arr[i][j] <<
" ";
45 }
46 cout <<
endl;
47 }
48 for(i = x_len, j = y_len; i >=
1 && j >=
1;)
49 {
50 if(str1[i -
1] == str2[j -
1])
51 {
52 cout << str1[i -
1] <<
" ";
//倒序打印的
53 i--
;
54 j--
;
55 }
56 else
57 {
58 // if(arr[i][j -1] >= arr[i - 1][j])//打印：B A D B
59 if(arr[i][j -
1] > arr[i -
1][j])
//打印:A B C B
60 {
61 j--
;
62 }
63 else
64 {
65 i--
;
66 }
67 }
68 }
69 cout <<
endl;
70 return 0;
71 }
C++
运行结果：
转载于:https://www.cnblogs.com/CoolRandy/p/3648977.html
相关资源：JAVA上百实例源码以及开源项目
