How to check if two string are a partial match in C#?

Question

Possible Duplicate:
Are there any Fuzzy Search or String Similarity Functions libraries written for C#?

I am creating an application which will except user input of a Song or Artist or Album name and then will look through a String Array or ArrayList for any possible matches.

The auto suggestions will be calculated based on the match percentage.

For example

If user types link prk it should find Linkin Park or Link 80 or Link Wray but the match percentage will be different for all

Assume that the collection will only search for Artist names in Artist Collection and Song name in song collection.

(Percentage figures are just for explanation)

Linkin Park - 98%
Link Wray -82%
Link 80 - 62%

Solution does not have to be C# code, any regex or pseudo code will be good but should be implementable in C#.

Answer 1

Usually an implementation of the Levenshtein distance also called edit distance is used for this. This will find matches based on the minimum number of edits needed to transform one string into the other, counting all insertions, deletions, or substitutions of a single character as a measure for the "cost" - candidates are then strings that have the minimum cost.

Here's a link to an article with a generic implementation in C#.

Answer 2

You're looking for Levenshtein distance

Here is an implementation in C#.

Here is a Generic Implementation of the Levenshtein Distance. (as in the Diff/Dist. between two IEnum<T> 's)

Implementations of Levenshtein Distance Algorithm in a LOT of languages.