Go语言视频零基础入门到精通

javalearner

最长公共子序列问题：
    给定两个序列 X = {x1, x2, ......, xm } 和 Y = {y1, y2, ......, yn }，找出 X 和 Y 的最长公共子序列。
一个给定序列的子序列是在该序列中删去若干个元素后得到的序列。给定两个序列 X 和 Y ，当另一序列 Z 既是 X 的子序列又是 Y 的子序列时，称 Z 是序列 X 和 Y 的公共子序列。
例如，若 X = {A， B， C， B， D， A， B }， Y = {B， D， C， A， B， A }，
序列{B， C， A }是 X 和 Y 的一个公共子序列，序列{B， C， B， A }也是 X 和 Y 的一个公共子序列，且为最长公共子序列。  最长公共子序列问题具有最优子结构性质。  设序列 X = {x1, x2, ......, xm } 和 Y = {y1, y2, ......, yn }的最长公共子序列为 Z = {z1, z2, ......, zk}
则（1） 若 xm = yn ，则 zk = xm = yn ，且 Zk-1 是 Xm-1 和 Yn-1 的最长公共子序列。
（2） 若 xm != yn 且 zk != xm ，则 Z 是 Xm-1 和 Y 的最长公共子序列。
（3） 若 xm != yn 且 zk != yn ，则 Z 是 X 和 Yn-1 的最长公共子序列。
其中:
Xm-1 = {x1, x2, ......, xm-1 }； Yn-1 = {y1, y2, ......, yn-1}； Zk-1 = {z1, z2, ......, zk-1}。
   引进一个二维数组C，用C[i,j]记录X与Y的LCS的长度,如果我们是自底向上进行递推计算，那么在计算C[i,j]之前，
C[i-1,j-1], C[i-1,j]与C[i,j-1]均已计算出来。此时我们根据X=Y[j]还是X≠Y[j]，就可以计算出C[i,j]： 若X=Y[j]，则执行C[i,j]=C[i-1,j-1]+1；若X≠Y[j]，则根据： C[i-1,j]≥C[i,j-1]，则C[i,j]取C[i-1,j]；否则C[i,j]取C[i,j-1]。
  为了构造出LCS，使用一个m×n的二维数组b，b[i,j]记录C[i,j]是通过哪一个子问题的值求得的,以决定搜索的方向：
若X=Y[j]，则b[i,j]中记入“1”； 若C[i-1,j]≥C[i,j-1]，则b[i,j]中记入“0”； 若C[i-1,j] < C[i,j-1]，则b[i,j]中记入“-1”；
为节省空间，数组b亦可不用，直接根据X=Y[j]还是X≠Y[j]以及C[i,j-1]，C[i-1,j]来找出搜索方向.

1. import java.util.Random;
   
2. public class LCS {
   
3.     public static void main(String[] args) {
   
4.         //设置字符串长度
   
5.         int substringLength1 = 100;
   
6.         int substringLength2 = 100;
   
7.         // 随机生成字符串
   
8.         String x = GetRandomStrings(substringLength1);
   
9.         String y = GetRandomStrings(substringLength2);
   
10.         Long startTime = System.nanoTime();
    
11.         // 构造二维数组记录子问题x[i]和y[i]的LCS的长度
    
12.         int[][] opt = new int[substringLength1 + 1][substringLength2 + 1];
    
13.         // 动态规划计算所有子问题
    
14.         for (int i = substringLength1 - 1; i >= 0; i--) {
    
15.             for (int j = substringLength2 - 1; j >= 0; j--) {
    
16.                 if (x.charAt(i) == y.charAt(j))
    
17.                     opt[i][j] = opt[i + 1][j + 1] + 1;
    
18.                 else
    
19.                     opt[i][j] = Math.max(opt[i + 1][j], opt[i][j + 1]);
    
20.             }
    
21.         }
    
22.         System.out.println("substring1:"+x);
    
23.         System.out.println("substring2:"+y);
    
24.         System.out.print("LCS:");
    
25.         int i = 0, j = 0;
    
26.         while (i < substringLength1 && j < substringLength2) {
    
27.             if (x.charAt(i) == y.charAt(j)) {
    
28.                 System.out.print(x.charAt(i));
    
29.                 i++;
    
30.                 j++;
    
31.             } else if (opt[i + 1][j] >= opt[i][j + 1])
    
32.                 i++;
    
33.             else
    
34.                 j++;
    
35.         }
    
36.         Long endTime = System.nanoTime();
    
37.         System.out.println(" Totle time is " + (endTime - startTime) + " ns");
    
38.     }
    
39.     //取得定长随机字符串
    
40.     public static String GetRandomStrings(int length) {
    
41.         StringBuffer buffer = new StringBuffer("abcdefghijklmnopqrstuvwxyz");
    
42.         StringBuffer sb = new StringBuffer();
    
43.         Random r = new Random();
    
44.         int range = buffer.length();
    
45.         for (int i = 0; i < length; i++) {
    
46.             sb.append(buffer.charAt(r.nextInt(range)));
    
47.         }
    
48.         return sb.toString();
    
49.     }
    
50. }

复制代码

   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/11/30/000658718.zip