如题:求两个序列的最长公共序列。(如:“ABCBDAB”与“BCDB”最长公共序列为"BCDB")代码如下:
#define MAX_SIZE 200char a[MAX_SIZE], b[MAX_SIZE], str[MAX_SIZE];int num[MAX_SIZE][MAX_SIZE];//计算最优值,即最长公用字符串的长度int lcs_len(int a_length, int b_length){ int t, s; if (a_length == 0 || b_length == 0) num[a_length][b_length] = 0; else if (a[a_length - 1] == b[b_length - 1]) num[a_length][b_length] = lcs_len(a_length - 1, b_length - 1) + 1; else { t = lcs_len(a_length, b_length - 1); s = lcs_len(a_length - 1, b_length); if (t > s) num[a_length][b_length] = t; else num[a_length][b_length] = s; } return num[a_length][b_length];}//找出字符串(注意:此方法只能找出字符串中的一种)void lcs_str(int str_len, int a_len, int b_len){ if ((!a_len) || (!b_len)) return; if (num[a_len][b_len] == num[a_len - 1][b_len]) lcs_str(str_len, a_len - 1, b_len); else if (num[a_len][b_len] == num[a_len][b_len - 1]) lcs_str(str_len, a_len, b_len - 1); else { str[str_len - 1] = a[a_len - 1]; lcs_str(str_len - 1, a_len - 1, b_len - 1); }}
仅供学习记录。