LCS(Longest Common Sequence), Java/C实现

import java.util.Stack;

// only print out the number that two arrays share the most common elements

public class LCS1 {
    // return common's number

    static int lcs(int a[], int ae, int b[], int be, Stack<Integer> cs) {
        if (ae < 0 || be < 0) {
            int s = cs.size();
            if (s > 0)
                cs.pop();
            return s;
        }
        if (a[ae] == b[be]) {
            cs.push(a[ae]);
            return lcs(a, ae - 1, b, be - 1, cs);
        } else {
            return Math.max(lcs(a, ae - 1, b, be, cs),
                    lcs(a, ae, b, be - 1, cs));
        }
    }

    public static void main(String[] args) {
        System.out.println(lcs(new int[] { 1, 3, 5, 6, 7, 8, 9 }, 6, new int[] {
                2, 3, 6, 9 }, 3, new Stack<Integer>()));
    }
}


#include <stdio.h>

int cur_longest = 0;
int lcs_ar[20];
int plcs = 0;

int cs[20];
int pcs = 0;

void lcs(int a[], int ae, int b[], int be)
{
        if (ae < 0 || be < 0)
        {
                if (pcs > cur_longest)
                {
                        int i = 0;
                        plcs = 0;
                        while (i < pcs)
                        {
                            lcs_ar[plcs] = cs[i];
                            i++;
                            plcs++;
                        }
                        cur_longest = pcs;
                }
                pcs--;
                return;
        }
        if (a[ae] == b[be])
        {
            cs[pcs] = a[ae];
            pcs++;
            lcs(a, ae - 1, b, be - 1);
        } else {
            lcs(a, ae - 1, b, be);
            lcs(a, ae, b, be - 1);
        }
}

int main()
{
    int a[] = {1,3,5,6,7,8,9,10,9};
    int b[] = {2,3,6,9,9};
    lcs(a, 8, b, 4);
    while(plcs > 0)
    {
        printf("%d ", lcs_ar[plcs-1]);
        plcs--;
    }
    printf("\n");
    return 0;
}


#include <stdio.h>

char a[] = {'\0','a','b','c','b','d','a','b'};
#define a_len 7
char b[] = {'\0','b','d','c','a','b','a'};
#define b_len 6

int c[a_len+1][b_len+1];
int p[a_len+1][b_len+1];

#define UPLEFT 3
#define UP 2
#define LEFT 1

void lcs_length(char a[], int alength, char b[], int blength)
{
        int i = 0;

        for (i = 0; i <= alength; i++)
        {
                c[i][0] = 0;
        }
        for (i = 0; i<= blength; i++)
        {
                c[0][i] = 0;
        }

        int j = 0;

        for (i = 1; i <= alength; i++)
        {
                for (j = 1; j<= blength; j++)
                {
                        if (a[i] == b[j])
                        {
                                c[i][j] = c[i-1][j-1] + 1;
                                p[i][j] = UPLEFT;
                        }
                        else
                        {
                                if (c[i-1][j] >= c[i][j-1])
                                {
                                        c[i][j] = c[i-1][j];
                                        p[i][j] = UP;
                                }
                                else
                                {
                                        c[i][j] = c[i][j-1];
                                        p[i][j] = LEFT;
                                }
                        }
                }
        }
}

void print_lcs(char a[], int a_start, int a_end, char b[], int b_start, int b_end)
{
        if (a_end < a_start || b_end < b_start)
        {
                return;
        }
        if (p[a_end][b_end] == UPLEFT)
        {
                print_lcs(a, a_start, a_end - 1, b, b_start, b_end - 1);
                printf("%c", a[a_end]);
        }
        else if (p[a_end][b_end] == UP)
        {
                print_lcs(a, a_start, a_end-1, b, b_start, b_end);
        }
        else
        {
                print_lcs(a, a_start, a_end, b, b_start, b_end-1);
        }
}

int main()
{
        lcs_length(a, a_len, b, b_len);
        print_lcs(a, 1, a_len, b, 1, b_len);
        return 1;
}