动态规划求最大公共字串
动态规划-----求两个字符串的最大公共字串

package zju;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class SameString {public static void main(String[] args){String s1="";        String s2="";        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));        System.out.println("Please Input the two strings:");        try {s1=br.readLine();s2=br.readLine();    br.close();} catch (IOException e) {e.printStackTrace();}               SameString ss=new SameString();        System.out.println("The longest same string is:"+ss.findSameStr(s1, s2));}public  String findSameStr(String str1,String str2){int len1=str1.length();int len2=str2.length();int max=0; //字符串最大长度int current=0;//记录str1的当前位置char[] c1=str1.toCharArray();       char[] c2=str2.toCharArray();int[][] c=new int[len1][len2];//用于记录公共字串的数组//初始化for(int i=0;i<len1;i++){c[i][0]=0;}for(int j=0;j<len2;j++){c[0][j]=0;}for(int i=0;i<len1;i++){for(int j=0;j<len2;j++){if(c2[j]==c1[i]){if(i==0||j==0){c[i][j]=1;if(max<c[i][j]){    max=c[i][j];    current=i;    }}else{    c[i][j]=c[i-1][j-1]+1;    if(max<c[i][j]){    max=c[i][j];    current=i;    }}}}}       /*//输出数组c for(int i=0;i<c1.length;i++){     for(int j=0;j<c2.length;j++){    System.out.print(" "+c[i][j]);        }     System.out.println("");     }*/ String str="";//str存放最长公共字串if(max>0){for(int k=current-max+1;k<=current;k++){char ch=c1[k];       str+=String.valueOf(ch);}}return str;}    }