1458 Common Subsequence

「1458 Common Subsequence」の編集履歴(バックアップ)一覧はこちら

1458 Common Subsequence」(2006/04/17 (月) 01:43:22) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

**1458 Common Subesequence **問題 http://acm.pku.edu.cn/JudgeOnline/problem?id=1458 **解答方針 最長共通部分列問題. **解答例 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()){ String s1 = sc.next(); String s2 = sc.next(); Solver sol = new Solver(s1,s2); System.out.println(sol.solve()); } } } class Solver{ String s1; String s2; Solver(String is1,String is2){ s1 = is1; s2 = is2; } public int solve(){ int len1 = s1.length(); int len2 = s2.length(); int[][] table = new int[len1+1][len2+1]; for(int i=0;i<=len1;i++) table[i][0] = 0; for(int j=0;j<=len2;j++) table[0][j] = 0; for(int k=1;k<=Math.min(len1,len2);k++){ if(s1.charAt(k-1)==s2.charAt(k-1)){ table[k][k] = max3(table[k-1][k-1]+1,table[k][k-1],table[k-1][k]); } else{ table[k][k] = max3(table[k-1][k-1],table[k][k-1],table[k-1][k]); } for(int i=k+1;i<=len1;i++){ if(s1.charAt(i-1)==s2.charAt(k-1)){ table[i][k] = max3(table[i-1][k-1]+1,table[i][k-1],table[i-1][k]); } else{ table[i][k] = max3(table[i-1][k-1],table[i][k-1],table[i-1][k]); } } for(int j=k+1;j<=len2;j++){ if(s1.charAt(k-1)==s2.charAt(j-1)){ table[k][j] = max3(table[k-1][j-1]+1,table[k][j-1],table[k-1][j]); } else{ table[k][j] = max3(table[k-1][j-1],table[k][j-1],table[k-1][j]); } } } return table[len1][len2]; } public static int max3(int x,int y,int z){ return Math.max(x,Math.max(y,z)); } }

表示オプション

横に並べて表示:
変化行の前後のみ表示:
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。