Application Developer Festival 2015 コーディング自己紹介
入力文字列と自分の名前のLCSをDPで求める。
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); char[] input = scanner.next().toCharArray(); scanner.close(); int N = input.length; String myString = "kenkonakamura"; char[] name = myString.toCharArray(); int M = name.length; int[][] dp = new int[N + 1][M + 1]; // Longest Common Subsequence for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (input[i] == name[j]) { dp[i + 1][j + 1] = Math.max(dp[i][j] + 1, dp[i + 1][j + 1]); } else { dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]); } } } // 戻すDP int i = N; int j = M; StringBuilder sb = new StringBuilder(); while (i > 0 && j > 0) { if (dp[i][j] > dp[i - 1][j - 1]) { if (j == 1) { sb.append("K"); } else if (j == 6) { sb.append("N"); } else { sb.append(name[j - 1]); } i--; j--; } else { j--; } } sb.reverse(); System.out.println(sb.toString()); } }