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());

	}
}