文字列の最大共通サブシーケンスおよび最大共通サブ列の問題
3481 ワード
最大共通サブシーケンス
最大共通サブストリング
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));
}