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