package?最長公共子序列;

public?class?LCS?{
	public?static?void?main（String[]?args）?{
		
		
		//↖←↑
		?
		?String?[]?X={“A““B““C““B““D““A““B“};
		?String??[]?Y={“B““D““C““A““B““A“};
		?LCS（XYX.lengthY.length）;
		?
		

	}
????????public?static?void?LCS（String?[]XString?[]Yint?mint?n）
????????{
????????	int[][]C=new?int?[m+1][n+1];
????????	String[][]B=new?String?[m+1][n+1];
????????	for（int?i=0;i<=m;i++）
????????	{
????????		C[i][0]=0;
????????	}
????????	for（int?i=0;i<=n;i++）
????????	{
????????		C[0][i]=0;
????????	}
????????	for（int?i=1;i<=m;i++）
????????	{
????????		for（int?j=1;j<=n;j++）
????????		{
????????			if（X[i-1]==Y[j-1]）{
????????				C[i][j]=C[i-1][j-1]+1;
????????				B[i][j]=“↖“;
????????			}
????????			else?if（C[i-1][j]>=C[i][j-1]）{
????????				C[i][j]=C[i-1][j];
????????				B[i][j]=“↑“;
????????			}
????????			else
????????			{
????????				C[i][j]=C[i][j-1];
????????				B[i][j]=“←“;
????????			}
????????		}
????????	}
????????	
????????	//測試
????????	for（int?i=1;i<=m;i++）
????????	{
????????		for（int?j=1;j<=n;j++）
????????		{
????????			System.out.print（C[i][j]+““+“B[“+i+“][“+j+“]=“+B[i][j]+“\t“）;
????????		}
????????		System.out.println（）;
????????	}
????????	StructureSequence（BXmn）;
????????	
????????	
????????}
????????
????????
????????public?static?void?StructureSequence（String?[][]BString[]?Xint?iint?j）{
????????	if（i==0||j==0）{
????????		return;
????????	}
????????	if（B[i][j]==“↖“）{
????????		System.out.println（X[i-1]）;
????????		StructureSequence（BXi-1j-1）;
????????	}
????????	else?if（B[i][j]==“↑“）{
????????		StructureSequence（BXi-1j）;
????????	}
????????	else{
????????		StructureSequence（BXij-1）;
????????	}
????????		
????????}
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????1802??2017-11-18?15:16??LCS.java

-----------?---------??----------?-----??----

?????????????????1802????????????????????1