Good String Matching Algorithm

[Cheetah Designs]

Hi there,

I need a good string matching algorithm, so it finds the closest match out of a list of strings.

Eg.

So If i had a list like this:

myStrings[0] = "The Next Door"
myStrings[1] = "The Next Time"
myStrings[2] = "Next Friday / Friday After Next"
myStrings[3] = "Next (r)"
myStrings[4] = "Advance to the Next Level"

and I was searching for "Next"....it would return myStrings[3].

I am currently developing in VB.NET but would probably be able to convert from c#.net or php.

Thanks.

EDIT: Basically, I am looking for a search algorithm/function

 

[Sic]

look up:

regular expressions
preg_match_all() - php function

 

[Inquisitor]

look up:

regular expressions
preg_match_all() - php function

That won't give weighting, though.

 

[Ladforce]

In managed c++ you can use System::String::IndexOf(String^ string) which will return the index of the string searched for. You could compare all indexes and the lowest would be the closest match. Basic but would give you the answer you want. I believe there is a similar/same function in c#.net.

 

[Cheetah Designs]

Thanks for the replies guys. This is something some has produced for me, which I have adapted slightly he was practising more complex coding structures which weren't needed:

Basically you pass in options, which has the search term and the list to search:

        'Creates an array to store the results as they come in.  As percentages
        Dim Percentages(Options.List.Count) As Double
        Dim matchedWords(Options.List.Count) As Integer

        'Two loops.  First we loop through each word (Separated by a space).  Next we search each item with the
        'search term.  If we have a match then we add to the percentage for that item.
        For Each SearchTerm As String In Options.SearchString.Split(" "c)
            For i As Integer = 0 To Options.List.Count - 1
                Dim Item As String = LCase(CStr(Options.List(i)))
                If Item.IndexOf(LCase(SearchTerm)) <> -1 Then
                    Percentages(i) += SearchTerm.Length / Item.Length
                    matchedWords(i) += 1
                Else
                    matchedWords(i) -= 1
                End If
                For Each item2 As String In Item.Split(" "c)
                    If LCase(Options.SearchString).Contains(LCase(item2)) = False Then
                        matchedWords(i) -= 1
                    End If
                Next
            Next
        Next

        ''Check if there are any extra words on the results returned by the search and take away matched words.
        'For Each item As String In Options.List
        '    For Each item2 As String In item.Split(" "c)
        '        If LCase(Options.SearchString).Contains(LCase(item2)) = False Then
        '            matchedWords(i) -= 1
        '        End If
        '    Next
        'Next

        'All we are doing here is finding the index of the highest percentage.
        Dim HighestPercentageIndex, HighestMatchedWords As Integer, HighestPercentageValue As Double
        HighestPercentageIndex = -1
        HighestPercentageValue = -1
        HighestMatchedWords = -1
        For i As Integer = 0 To Percentages.GetUpperBound(0)
            If (Percentages(i) > HighestPercentageValue) And (matchedWords(i) > HighestMatchedWords) Then
                HighestPercentageIndex = i
                HighestMatchedWords = matchedWords(i)
                HighestPercentageValue = Percentages(i)
            End If
        Next

 

[Sic]

That won't give weighting, though.

preg_match_all will return the amount of times a pattern is matched, so it kinda will