动态规划求最大公共字串
动态规划-----求两个字符串的最大公共字串
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;} }