最長連続共通サブシーケンス---動的計画
1994 ワード
2つの文字列について、最も長い共通サブシーケンスの長さを求める効率的なアルゴリズムを設計し、文字が連続して与えられた文字列AとBを必要とせず、最も長い共通サブシーケンスの長さを返します.2つの列の長さが300以下であることを保証します.試験例:1 A 2 C 3 D 4 B 56 B 1 D 23 CA 45 B 6 A戻り:6
public class {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String A=sc.next();
String B=sc.next();
sc.close();
int n=A.length();
int m=B.length();
char a[]=A.toCharArray();
char b[]=B.toCharArray();
int[][] dp=new int[n + 1][m + 1];
// A i B j
for (int i=1;i<=n;i++) {
for (int j=1;j<= m;j++){
if (a[i-1]==b[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
}else{
dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
System.out.println(dp[n][m]);
}
}