public class SequenceAlignment {
	public static void main(String[] args) {
		System.out.println("Result is: " + getSimilarityScore("ATCCGT", "TTCTGT"));
	}

	public static int getSimilarityScore(String s1, String s2) {
		int[][] possibleSolutions = new int[s1.length() + 1][s2.length() + 1];
		// initialize matrix
		for (int i = 0; i < (s1.length() + 1); i++) {
			possibleSolutions[i][0] = i * -1;
		}
		for (int i = 0; i < (s2.length() + 1); i++) {
			possibleSolutions[0][i] = i * -1;
		}
		// dynamic programming
		for (int i = 1; i < s1.length() + 1; i++) {
			for (int j = 1; j < s2.length() + 1; j++) {
				possibleSolutions[i][j] = Math.max(possibleSolutions[i][j - 1] - 1,
						Math.max(possibleSolutions[i - 1][j] - 1, s1.charAt(i - 1) == s2.charAt(j - 1)
								? possibleSolutions[i - 1][j - 1] + 2 : possibleSolutions[i - 1][j - 1] - 1));
			}
		}
		// print matrix
		for (int i = 0; i < s1.length() + 1; i++) {
			for (int j = 0; j < s2.length() + 1; j++) {
				System.out.print(possibleSolutions[i][j] + "\t");
			}
			System.out.println();
		}
		return possibleSolutions[possibleSolutions.length - 1][possibleSolutions[0].length - 1];
	}
}