字符串最大公共子序列以及最大公共子串问题

最大公共子序列

import java.util.Random;
public class LCS {

	public static void main(String[] args){

        //设置字符串长度
        int substringLength1 = 20;
        int substringLength2 = 20;  //具体大小可自行设置

        // 随机生成字符串
        String x = GetRandomStrings(substringLength1);
        String y = GetRandomStrings(substringLength2);
        // 构造二维数组记录子问题x[i]和y[i]的LCS的长度
        int[][] opt = new int[substringLength1 + 1][substringLength2 + 1];

        // 从后向前，动态规划计算所有子问题。也可从前到后。
        for (int i = substringLength1 - 1; i >= 0; i--){
            for (int j = substringLength2 - 1; j >= 0; j--){
               if (x.charAt(i) == y.charAt(j))
                   opt[i][j] = opt[i + 1][j + 1] + 1;//状态转移方程                                 
                else
                    opt[i][j] = Math.max(opt[i + 1][j], opt[i][j + 1]);//状态转移方程       
            }
        }
        System.out.println("substring1:"+x);
        System.out.println("substring2:"+y);
        System.out.print("LCS:");

        int i = 0, j = 0;
        while (i < substringLength1 && j < substringLength2){
            if (x.charAt(i) == y.charAt(j)){
                System.out.print(x.charAt(i));
                i++;
                j++;
            } else if (opt[i + 1][j] >= opt[i][j + 1])
                i++;
            else
                j++;
        }
    }

    //取得定长随机字符串
    public static String GetRandomStrings(int length){
        StringBuffer buffer = new StringBuffer("abcdefghijklmnopqrstuvwxyz");
        StringBuffer sb = new StringBuffer();
        Random r = new Random();
        int range = buffer.length();
        for (int i = 0; i < length; i++){
            sb.append(buffer.charAt(r.nextInt(range)));
        }
        return sb.toString();
    }    
}

最大公共子串

public static void lcs2(){
        String x="abcdepoi";
        String y="bcdefpoi";
    	int substringLength1 = x.length();
        int substringLength2 = y.length(); 
        int opt[][]=new int [substringLength1+1][substringLength2+1];
        for(int i=1;i<=substringLength1;i++)
        	for(int j=1;j<=substringLength2;j++)
        	{
        		if(x.charAt(i-1)==y.charAt(j-1))
        			opt[i][j]=opt[i-1][j-1]+1;//状态转移方程，
        	}
        int max=opt[0][0];
        int m=0,n=0;
        for(int i=substringLength1;i>=1;i--)
        	for(int j=substringLength2;j>=1;j--){
        		if(opt[i][j]>max)
        			{
        				max=opt[i][j];
        				m=i;
        				n=j;
        			}
        	}
        System.out.println("x = "+x);
        System.out.println("y = "+y);
        System.out.println("max = "+max);
        StringBuffer sb=new StringBuffer();
        for(int i=m,j=n;i>=1&&j>=1;i--,j--)
    		{
        		if(opt[i][j]>0)
        			sb.append(x.charAt(i-1));
    		}
        String result=sb.toString();
        for(int i=result.length()-1;i>=0;i--)
        	System.out.print(result.charAt(i));
    }