VB.net compare a full string to one containing wildcard characters

Question

I have a method that takes 2 string arguments. One that contains a normal string and one that contains a string with one or more wildcard characters. I've tried the following code:

Private Function DoesMatchWildcardString(ByVal fullString As String, ByVal wildcardString As String) As Boolean
    Dim stringParts() As String
    Dim matches As Boolean = True

    stringParts = wildcardString.Split("*")

    For Each str As String In stringParts
        If fullString.Contains(str) = False Then
            matches = False
        End If
    Next

    Return matches

End Function

The I realized that it won't work properly. If I have ABCD as a normal and A*CD as my wildcard string the match will work even if my normal string was CDAB, which is not what I want.

Any ideas??

Thanks a lot.

Answer 1

Your approach is interesting but very inefficient even once corrected. An efficient implementation of the wildcard matching algorithm uses an extension of the shift-or algorithm (according to Wikipedia also called “bitap” by some sources, but I’ve never read that myself).

The only change to the conventional shift-or algorithm is in the preprocessing: For each * that you encounter in the pattern, enable all characters in the alphabet at this position.

If you want to correct your own algorithm, then replace the Contains call by IndexOf, and supply the position where it should start searching – namely, after the previous match. This will work for most cases, but it will perform a non-greedy search which might fail in some circumstances. An exhaustive search will necessarily backtrack. As I said, that’s inefficient, and the shift-or algorithm doesn’t suffer from this shortcoming.

But all of this is unnecessary since VB already provides the necessary operator: Like

If fullString Like wildcardString Then
    ' Yep, matches.
End If

---

A note on style:

Always initialise variables when you declare them, do not separate declaration and initialisation needlessly.

That is, write

Dim stringParts As String() = wildcardString.Split("*")
' or, with Option Infer On:
Dim stringParts = wildcardString.Split("*")

Furthermore, it makes no sense to compare a Boolean with a literal (If X = False …). Just write

If fullString.Contains(str) Then