Levenshtein Distance

Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (i.e. insertions, deletions or substitutions) required to change one word into the other. It is named after Vladimir Levenshtein, who considered this distance in 1965.

• C#
• VB.Net
• C
• C++
• PHP

									/*****Please include following header files*****/
// string
/***********************************************/

/*****Please use following namespaces*****/
// std
/*****************************************/

#define MIN3(a, b, c) ((a) < (b) ? ((a) < (c) ? (a) : (c)) : ((b) < (c) ? (b) : (c)))

static int LevenshteinDistance(string s1, string s2) {
	unsigned int s1len, s2len, x, y, lastdiag, olddiag;
	s1len = s1.size();
	s2len = s2.size();
	unsigned int* column = new unsigned int[s1len + 1];

	for (y = 1; y <= s1len; ++y)
		column[y] = y;

	for (x = 1; x <= s2len; ++x)
	{
		column[0] = x;

		for (y = 1, lastdiag = x - 1; y <= s1len; ++y)
		{
			olddiag = column[y];
			column[y] = MIN3(column[y] + 1, column[y - 1] + 1, lastdiag + (s1[y - 1] == s2[x - 1] ? 0 : 1));
			lastdiag = olddiag;
		}
	}

	return(column[s1len]);
}
								

Example

									int result = LevenshteinDistance("kitten", "sitting");
								

Output

									result: 3