算法-最长公共子序列

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/*
 * @Author: MetaNetworks
 * @Date: 2019-10-31 11:34:11
 * @LastEditors: MetaNetworks
 * @LastEditTime: 2019-10-31 15:24:25
 * @Description: MetaNetworks' Code
 */
#include <iostream>
#include <stdlib.h>
#include <stack>
#define NUM 5
#define NOTSET -1
using namespace std;

char str_a[] = " CBDCA";
char str_b[] = " BDCAB";
// 字符串在 0-4，5是反斜杠0,也是无效字符
int mat[NUM+1][NUM+1];

int cal(int x,int y){
    if (mat[x][y] == NOTSET)
    {
        if (str_a[x-1]==str_b[y-1])
        {
            mat[x][y] = cal(x-1,y-1) + 1;
        }
        else{
            mat[x][y] = max(cal(x-1,y),cal(x,y-1));
        }
    }
    return mat[x][y];
}

stack<int> s;
void getIndex(int x,int y){
    while(mat[x][y]!=0){
        if(str_a[x]==str_b[y]){
            // 相等则 往stack传入x
            s.push(x);
            getIndex(x-1,y-1);
        }
        else{
            // 不等,则由最大的继承
            if(mat[x-1][y]>mat[x][y-1]){
                getIndex(x-1,y);
            }
            else{
                getIndex(x,y-1);
            }
        }
        return;
    }
    // 输出
    while (!s.empty())
    {
        int index = s.top();
        cout<<str_a[index];
        s.pop();   
    }
}

int main(){
    // reset to 0
    for (int j = 0; j <= NUM; j++)
    {
        for(int k=0;k <= NUM;k++){
            mat[j][k] = NOTSET;
        }
    }
    // 0
    for (int i = 0; i <= NUM; i++)
    {
        mat[0][i] = 0;
        mat[i][0] = 0;
    }
    cout<<cal(NUM,NUM)<<endl;
    for (int j = 0; j <= NUM; j++)
    {
        for(int k=0;k<=NUM;k++){
            cout<<mat[j][k]<<" ";
        }
        cout<<endl;
    }
    getIndex(NUM,NUM);
}