最长公共子序列算法问题JAVA源代码免费下

import java io BufferedReader import java io IOException import java io InputStreamReader import java util ArrayList import java util Scanner import java util List 动态规划法解最长公共子系列 author 蓝冠恒 public class LCS public static List resultList new ArrayList 计算最优值 param x 字符系列数组 param y 字符系列数组 param c 存储x和y最长公共子系列长度数组 param b 记录c中元素对应子问题的解的数组 public static void lcsLength char x char y int c int b int m x length 1 int n y length 1 resultList clear 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 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 public static void lcs int i int j char x int b if i 0 j 0 return if b i j 1 lcs i 1 j 1 x b resultList add x i else if b i j 2 lcs i 1 j x b else lcs i j 1 x b public static void main String arg String a String input char x char y Scanner scan new Scanner System in BufferedReader in new BufferedReader new InputStreamReader System in do try do System out println 请输入第一串字符系列 input in readLine trim while input equals input S input x input toCharArray do System out println 请输入第二串字符系列 input in readLine trim while input equals input S input y input toCharArray int b new int x length y length int c new int x length y length lcsLength x y c b 计算最优值 lcs x length 1 y length 1 x b 构造最长公共子系列 int size resultList size System out print 最长公共子系列为 for int i 0 i size i System out print resultList get i System out println n catch IOException e e printS