- package com.leejuen.string;
- import java.lang.reflect.Array;
- import java.util.Arrays;
- public class LCS
- {
- private Integer len;
- private Object str1;
- private Object str2;
- LCS(String a,String b)
- {
- //iniChar(a.toCharArray(), b.toCharArray());
- str1 = a.toCharArray();
- str2 = b.toCharArray();
- }
- LCS(char[] a,char[] b)
- {
- str1 = a;
- str2 = b;
- }
- LCS(int[] a,int[] b)
- {
- str1 = a;
- str2 = b;
- }
- public int getLCS()
- {
- if(len==null) ini();
- return len;
- }
- private void ini()
- {
- int str1_len = Array.getLength(str1);
- int str2_len = Array.getLength(str2);
- int[][] dp = new int[str1_len+1][str2_len+1]; //初始化dp,java默认数据为0所以不用赋值
- for(int i=1;i<=str1_len;i++)
- {
- for(int j=1;j<=str2_len;j++)
- {
- Object tmp1 = Array.get(str1, i-1);
- Object tmp2 = Array.get(str2, j-1);
- if(tmp1.equals(tmp2))
- {
- dp[i][j] = dp[i-1][j-1]+1;
- }
- else
- {
- dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
- }
- }
- }
- len = dp[str1_len][str2_len];
- }
- //一下是测试:打印4、5
- /*public static void main(String[] args)
- {
- //经典最长公共子序列
- String a = "BDCABA";
- String b = "ABCBDAB";
- System.out.println(new LCS(a,b).getLCS());
- //最长升序子序列
- int[] cc1 = {3,1,5,6,2,7,9};
- int[] cc2 = Arrays.copyOf(cc1, cc1.length);
- Arrays.sort(cc2);
- System.out.println(new LCS(cc1,cc2).getLCS());
- }*/
- }
- //该片段来自于http://www.codesnippet.cn/detail/2212201514265.html
来源: http://www.codesnippet.cn/detail/2212201514265.html