package my.spider;
/* Levenshtein in Java, from Josh Drew's code at
 * http://joshdrew.com/
 * I wrote this code to help my understanding of
 * the MySQL UDF code, but didn't actually use it
 * in any project. It is completely untested.
 * The MySQL UDF code seems to work very well:
 * http://blog.lolyco.com/sean/2008/08/06/search-suggestions-with-mysql-levenshtein-distance/
 *
 * October 2008 sean at lolyco.com
 */

public class Levenshtein
{
	public static int lev(String s, String t)
	{
		int m = s.length() + 1;
		int n = t.length() + 1;
		if (m == 1)
			return n - 1;
		if (n == 1)
			return m -1;
		int[] d = new int[m * n];
		for (int i = 0; i < n; i++)
			d[i] = i;
		int k = n;
		for (int i = 1; i < m; i++)
		{
			d[k] = i;
			k += n;
		}
		int f = 0, g = 0, h = 0, min = 0, b = 0, c = 0, cost = 0;
		for (int i = 1; i < n; i++)
		{
			k = i;
			f = 0;
			for (int j = 1; j < m; j++)
			{
				h = k;
				k += n;
				min = d[h] + 1;
				b = d[k - 1] + 1;
				if (g < s.length() && f < t.length())
					cost = s.charAt(g) == t.charAt(f)?0:1;
				else
					cost = 1;
				c = d[h - 1] + cost;
				if (b < min)
					min = b;
				if (c < min)
					min = c;
				d[k] = min;
				/*
				System.out.println("i=" + i + ", j=" + j);
				for (int v = 0; v < m; v++)
				{
					for (int w = 0; w < n; w++)
						System.out.print(d[v * n + w] + " ");
					System.out.println();
				}
				*/
				f = j;
			}
			g = i;
		}
		return d[k];

	}
	public static int levlim(String s, String t, int limit)
	{
		int m = s.length() + 1;
		int n = t.length() + 1;
		if (m == 1)
			return n - 1;
		if (n == 1)
			return m -1;
		int[] d = new int[m * n];
		for (int i = 0; i < n; i++)
			d[i] = i;
		int k = n;
		for (int i = 1; i < m; i++)
		{
			d[k] = i;
			k += n;
		}
		int f = 0, g = 0, h = 0, min = 0, b = 0, c = 0, best = 0, cost = 0;
		for (int i = 1; i < n; i++)
		{
			k = i;
			f = 0;
			best = limit;
			for (int j = 1; j < m; j++)
			{
				h = k;
				k += n;
				min = d[h] + 1;
				b = d[k - 1] + 1;
				if (g < s.length() && f < t.length())
					cost = s.charAt(g) == t.charAt(f)?0:1;
				else
					cost = 1;
				c = d[h - 1] + cost;
				if (b < min)
					min = b;
				if (c < min)
					min = c;
				d[k] = min;
				/*
				System.out.println("i=" + i + ", j=" + j);
				for (int v = 0; v < m; v++)
				{
					for (int w = 0; w < n; w++)
						System.out.print(d[v * n + w] + " ");
					System.out.println();
				}
				*/
				if (min < best)
					best = min;
				f = j;
			}
			if (best >= limit)
				return limit;
			g = i;
		}
		return d[k];

	}
	public static int damlev(String s, String t)
	{
		int l1 = s.length();
		int l2 = t.length();
		int m = l1 + 1;
		int n = l2 + 1;
		if (m == 1)
			return n - 1;
		if (n == 1)
			return m -1;
		int[] d = new int[m * n];
		int k = 0;
		for (int i = 0; i < n; i++)
			d[i] = i;
		k = n;
		for (int i = 1; i < m; i++)
		{
			d[k] = i;
			k += n;
		}
		int f = 0, g = 0, h = 0, min = 0, b = 0, c = 0, cost = 0, tr = 0;
		for (int i = 1; i < n; i++)
		{
			k = i;
			f = 0;
			for (int j = 1; j < m; j++)
			{
				h = k;
				k += n;
				min = d[h] + 1;
				b = d[k - 1] + 1;
				if (g < l1 && f < l2)
					if (s.charAt(g) == t.charAt(f))
						cost = 0;
					else
					{
						cost = 1;
						/* Sean's transposition */
						if (j < l2 && i < l1)
								if (s.charAt(i) == t.charAt(f) && s.charAt(g) == t.charAt(j))
								{
									tr = d[(h) - 1]/* + 1*/; // transposition yields deletion cost at next iteration?
									if (tr < min)
										min = tr;
								}
					}
				else
					cost = 1;
				c = d[h - 1] + cost;
				if (b < min)
					min = b;
				if (c < min)
					min = c;
				d[k] = min;
				/*
				System.out.println("i=" + i + ", j=" + j);
				for (int v = 0; v < m; v++)
				{
					for (int w = 0; w < n; w++)
						System.out.print(d[v * n + w] + " ");
					System.out.println();
				}
				*/
				f = j;
			}
			g = i;
		}
		return d[k];
	}
	public static int damlevlim(String s, String t, int limit)
	{
		int l1 = s.length();
		int l2 = t.length();
		int m = l1 + 1;
		int n = l2 + 1;
		if (m == 1)
			return n - 1;
		if (n == 1)
			return m -1;
		int[] d = new int[m * n];
		int k = 0;
		for (int i = 0; i < n; i++)
			d[i] = i;
		k = n;
		for (int i = 1; i < m; i++)
		{
			d[k] = i;
			k += n;
		}
		int f = 0, g = 0, h = 0, min = 0, b = 0, best = 0, c = 0, cost = 0, tr = 0;
		for (int i = 1; i < n; i++)
		{
			k = i;
			f = 0;
			best = limit;
			for (int j = 1; j < m; j++)
			{
				h = k;
				k += n;
				min = d[h] + 1;
				b = d[k - 1] + 1;
				if (g < l1 && f < l2)
					if (s.charAt(g) == t.charAt(f))
						cost = 0;
					else
					{
						cost = 1;
						/* Sean's transposition */
						if (j < l2 && i < l1)
								if (s.charAt(i) == t.charAt(f) && s.charAt(g) == t.charAt(j))
								{
									tr = d[(h) - 1]/* + 1*/; // transposition yields deletion cost at next iteration?
									if (tr < min)
										min = tr;
								}
					}
				else
					cost = 1;
				c = d[h - 1] + cost;
				if (b < min)
					min = b;
				if (c < min)
					min = c;
				d[k] = min;
				/*
				System.out.println("i=" + i + ", j=" + j);
				for (int v = 0; v < m; v++)
				{
					for (int w = 0; w < n; w++)
						System.out.print(d[v * n + w] + " ");
					System.out.println();
				}
				*/
				if (min < best)
					best = min;
				f = j;
			}
			if (best >= limit)
				return limit;
			g = i;
		}
		return d[k];
	}
	public static void main(String[] args) throws Exception
	{
		java.io.BufferedReader brIn = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
		String sIn = null;
		while (true)
		{
			System.out.println("Two words, separated by space: ");
			sIn = brIn.readLine();
			if (sIn == null)
				break;
			String[] asIn = sIn.split(" ");
			if (asIn.length != 2)
				continue;
			System.out.println("lev(" + asIn[0] + ", " + asIn[1] + ") = " + lev(asIn[0], asIn[1]));
			System.out.println("levlim(" + asIn[0] + ", " + asIn[1] + ", 3) = " + levlim(asIn[0], asIn[1], 3));
			System.out.println("damlev(" + asIn[0] + ", " + asIn[1] + ") = " + damlev(asIn[0], asIn[1]));
			System.out.println("damlevlim(" + asIn[0] + ", " + asIn[1] + ") = " + damlevlim(asIn[0], asIn[1], 3));
		}

	}
}