Pattern Matching with Wildcards

What is Pattern Matching with Wildcards?

Pattern Matching with Wildcards is an advanced search algorithm that extends traditional pattern matching by allowing wildcard characters ('*') to represent any sequence of characters (including empty sequence) during the search process. This approach is useful for flexible and efficient text searching in various applications.

Algorithm Steps

1. Initialization:

   • Prepare the pattern with wildcards and the text to search within.

2. Pattern Matching:

   • Iterate through the pattern and text character by character.
   • Handle wildcard characters ('*') to match any sequence of characters or positions.

3. Matching Strategy:

   • Use dynamic programming or a recursive approach to efficiently handle wildcard expansion and pattern matching.

Complexity Analysis

• Time Complexity: Depends on the specific implementation. It can range from $O(m \times n) )$ to $O(m + n)$, where $m$ is the length of the pattern and $n$ is the length of the text.
• Space Complexity: $O(m \times n) )$ in worst cases due to the potential recursion depth or dynamic programming table.

Example

Given a pattern with wildcards and a text:

pattern = "acd"
text = "abcd"

Using Pattern Matching with Wildcards:

• Match the pattern against the text, considering '*' as a wildcard that matches any sequence of characters.

Implementation

Python

def pattern_matching_with_wildcards(pattern, text):
    # Dynamic programming approach
    m, n = len(pattern), len(text)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    
    # Handle initial wildcard characters
    for i in range(1, m + 1):
        if pattern[i - 1] == '*':
            dp[i][0] = dp[i - 1][0]
    
    # Fill dp table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if pattern[i - 1] == '*':
                dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
            elif pattern[i - 1] == '?' or pattern[i - 1] == text[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
    
    return dp[m][n]

# Example usage:
pattern = "a*c*d"
text = "abcd"

if pattern_matching_with_wildcards(pattern, text):
    print(f"Pattern '{pattern}' matches text '{text}'")
else:
    print(f"Pattern '{pattern}' does not match text '{text}'")

C++

#include <iostream>
#include <vector>
#include <string>

bool pattern_matching_with_wildcards(const std::string& pattern, const std::string& text) {
    int m = pattern.size();
    int n = text.size();
    
    std::vector<std::vector<bool>> dp(m + 1, std::vector<bool>(n + 1, false));
    dp[0][0] = true;
    
    // Handle initial wildcard characters
    for (int i = 1; i <= m; ++i) {
        if (pattern[i - 1] == '*') {
            dp[i][0] = dp[i - 1][0];
        }
    }
    
    // Fill dp table
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (pattern[i - 1] == '*') {
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
            } else if (pattern[i - 1] == '?' || pattern[i - 1] == text[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    
    return dp[m][n];
}

int main() {
    std::string pattern = "a*c*d";
    std::string text = "abcd";
    
    if (pattern_matching_with_wildcards(pattern, text)) {
        std::cout << "Pattern '" << pattern << "' matches text '" << text << "'\n";
    } else {
        std::cout << "Pattern '" << pattern << "' does not match text '" << text << "'\n";
    }
    
    return 0;
}

Conclusion

Pattern Matching with Wildcards is a versatile algorithm that allows for flexible matching of patterns containing wildcard characters ('*') against text sequences. It is useful in various applications such as text processing, file search utilities, and more where flexible and efficient pattern matching is required.