[6] A wildcard matcher tests a wildcard pattern p against an input string s. It performs an anchored match, returns true only when p matches the entirety of s. The pattern can be based on any common syntax (see globbing), but on Windows programmers tend to only discuss a simplified syntax supported by the native C runtime:[7][8] This article mainly discusses the Windows formulation of the problem, unless otherwise stated.
Stated in zero-based indices, the wildcard-matching problem can be defined recursively as: where mij is the result of matching the pattern p against the text t truncated at i and j characters respectively.
Directly related problems in computer science include: Early algorithms for matching wildcards often relied on recursion, but the technique was criticized on grounds of performance[10] and reliability[8] considerations.
[10] The recursive algorithms are in general easier to reason about, and with the ABORT modification they perform acceptably in terms of worst-case complexity.
The following are developed by critics of the recursive algorithms: The following is not: The iterative functions above implement backtracking by saving an old set of pattern/text pointers, and reverting to it should a match fails.
Although non-recursive regular expression matchers such as Thompson's construction are less used in practice due to lack of backreference support, wildcard matching in general does not come with a similarly rich set of features.