avatar

算法-最长公共子串问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
using namespace std;
const int MAXN = 1000;
int c[MAXN][MAXN];
int b[MAXN][MAXN];
//1代表↖ 2代表↑ 3代表←
void LCSLength(char x[], int m, char y[], int n, int c[][MAXN], int b[][MAXN])
{
for(int i=1;i<=m;i++) c[i][0] = 0;
for(int i=1;i<=n;i++) c[0][i] = 0;

for(int i=1;i<=m;i++)
{
for(int 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 LCStraceback(int i, int j, char x[], int b[][MAXN])
{
if(i == 0 || j == 0) return;
if(b[i][j] == 1)
{
LCStraceback(i-1, j-1, x, b);
cout<<x[i];
}
else if(b[i][j] == 2) LCStraceback(i-1, j, x, b);
else LCStraceback(i, j-1, x, b);
}

int main()
{
char x[] = " ABCBDAB", y[] = " BADCDBA";
LCSLength(x, 7, y, 7, c, b);
for(int i=1;i<=7;i++)
{
for(int j=0;j<=7;j++)
cout<<c[i][j]<<" ";
cout<<endl;
}
LCStraceback(7, 7, x, b);
}
文章作者: 友人博
文章链接: http://abohelloworld.top/2020/04/04/%E6%9C%80%E5%A4%A7%E5%85%AC%E5%85%B1%E5%AD%90%E4%B8%B2%E9%97%AE%E9%A2%98/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 我的技术记录
打赏
  • 微信
    微信
  • 支付寶
    支付寶

评论