using System;


// Odleglosc Levenshteina (odleglosc edycyjna)
// www.algorytm.org
// (c) 2009 Tomasz Lubinski

namespace Levenshtein___CS
{
	/// <summary>
	/// Odleglosc Levenshteina (odleglosc edycyjna)
	/// www.algorytm.org
	/// (c) 2009 Tomasz Lubinski
	/// </summary>
	class Levenshtein
	{
		
		/// <summary>
		/// Odleglosc Levenshteina (odleglosc edycyjna)
		/// </summary>
		/// <param name="s">pierwszy ciag</param>
		/// <param name="t">drugi ciaf</param>
		/// <returns>Odleglosc Levenshteina</returns>
		private static int levenshtein(String s, String t)
		{
			int i, j, m, n, cost;
			int [,]d;

			m = s.Length;
			n = t.Length;
	   
			d = new int[m+1, n+1];

			for (i=0; i<=m; i++)
				d[i, 0] = i;
			for (j=1; j<=n; j++)
				d[0, j] = j;

			for (i=1; i<=m; i++)
			{
				for (j=1; j<=n; j++)
				{
					if (s[i-1] == t[j-1])
						cost = 0;
					else
						cost = 1;

					d[i, j] = Math.Min(d[i-1, j] + 1,   /* remove */
						Math.Min(d[i, j-1] + 1,         /* insert */
						   d[i-1, j-1] + cost));        /* change */
				}
			}

			return d[m, n];
		}

		/// <summary>
		/// Odleglosc Levenshteina (odleglosc edycyjna).
		/// </summary>
		[STAThread]
		static void Main(string[] args)
		{
			String s, t;

			Console.WriteLine("Podaj pierwszy ciag");
			s = Console.ReadLine();

			Console.WriteLine("Podaj drug ciag");
			t = Console.ReadLine();

			Console.WriteLine("Odleglosc Levenshteina wynosi: " + levenshtein(s, t));
		}
	}
}