动态规划求最大公共字串

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

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;
	}
    
}