public class StringMatch {

	public class coordinates
	{
		public int x;
		public int y;
	}
	
	private double[][] similarity;
	private boolean initialized = false;
	private static int blankPenalty = -10;
	private int width, height;
	public boolean saveMemory = false;
	
	private double euclideanDistance(int x1, int y1, int x2, int y2)
	{
		return Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2));
	}
	
	public void initialize(int width, int height)
	{
		similarity = new double[width*height][width*height];
		for(int i = 0; i < width*height; i++)
		{
			for(int j = 0; j < width*height; j++)
			{
				int y1 = j/width;
				int x1 = j%width;
				int y2 = i/width;
				int x2 = i%width;
				similarity[i][j] = euclideanDistance(x1, y1, x2, y2);
			}
		}
		this.width = width;
		this.height = height;
		initialized = true;
	}
	
	public double compare(coordinates[] A, coordinates[] B)
	{
		if(!saveMemory)
		{
			double score[][] = new double[A.length + 1][B.length + 1];
			for(int n = 0; n <= A.length; n++)
			{
				score[n][0] = n*blankPenalty;
			}
			for(int n = 0; n <= B.length; n++)
			{
				score[0][n] = n*blankPenalty;
			}
			for(int i = 1; i <= A.length; i++)
			{
				for(int j = 1; j <= B.length; j++)
				{
					double diag = score[i-1][j-1] + -1*((initialized) ? similarity[A[i-1].y*width + A[i-1].x][B[j-1].y*width + B[j-1].x] : euclideanDistance(A[i-1].x, A[i-1].y, B[j-1].x, B[j-1].y));
					double up = score[i-1][j] + blankPenalty;
					double left = score[i][j-1] + blankPenalty;
					if(diag >= up && diag >= left)
					{
						score[i][j] = diag;
					}
					else if(up >= left)
					{
						score[i][j] = up;
					}
					else
					{
						score[i][j] = left;
					}
				}
			}
			return score[A.length][B.length];
		}
		else
		{
			if(B.length < A.length)
			{
				coordinates[] temp = B;
				B = A;
				A = temp;
			}
			double score[][] = new double[2][A.length+1];
			for(int n = 0; n <= A.length; n++)
				score[0][n] = n*blankPenalty;
			for(int n = 1; n <= B.length; n++)
			{
				score[1][0] = n*blankPenalty;
				for(int k = 1; k <= A.length; k++)
				{
					double diag = score[0][k-1] + -1*((initialized) ? similarity[A[k-1].y*width + A[k-1].x][B[n-1].y*width + B[n-1].x] : euclideanDistance(A[k-1].x, A[k-1].y, B[n-1].x, B[n-1].y));
					double up = score[1][k-1] + blankPenalty;
					double left = score[0][k] + blankPenalty;
					if(diag >= up && diag >= left)
					{
						score[1][k] = diag;
					}
					else if(up >= left)
					{
						score[1][k] = up;
					}
					else
					{
						score[1][k] = left;
					}
				}
				double temp[];
				temp = score[1];
				score[1] = score[0];
				score[0] = temp;
			}
			return score[0][A.length];
		}
	}
	
//	public coordinates charToCoord(char c)
//	{
//		int x = (int)c;
//		coordinates y = new coordinates();
//		y.y = x/16;
//		y.x = x%16;
//		return y;
//	}
//	
//	private char coordToChar(coordinates a)
//	{
//		return (char) ((char)a.y*16 + a.x);
//	}
}