wildcard_matching.cpp File Reference

Implementation of the Wildcard Matching problem. More...

#include <cassert>
#include <iostream>
#include <vector>

Include dependency graph for wildcard_matching.cpp:

Namespaces
namespace	backtracking
	for vector container
namespace	wildcard_matching
	Functions for the Wildcard Matching problem.

Functions
bool	backtracking::wildcard_matching::wildcard_matching (std::string s, std::string p, uint32_t pos1, uint32_t pos2)
static void	test ()
	Self-test implementations.
int	main ()
	Main function.

Variables
std::vector< std::vector< int64_t > >	backtracking::wildcard_matching::dpTable (1000, std::vector< int64_t >(1000, -1))
	The main function implements if pattern can be matched with given string.

Detailed Description

Implementation of the Wildcard Matching problem.

Given a matching string and a pattern, implement wildcard pattern matching with support for ? and *. ? matches any single character. * matches any sequence of characters (including the empty sequence). The matching should cover the entire matching string (not partial). The task is to determine if the pattern matches with the matching string

Author

Swastika Gupta

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

           {
    test();  // run self-test implementations
    return 0;
}

Here is the call graph for this function:

test()

static void test ( )

static

Self-test implementations.

Returns

void

                   {
    // 1st test
    std::cout << "1st test ";
    std::string matching1 = "baaabab";
    std::string pattern1 = "*****ba*****ab";
    assert(backtracking::wildcard_matching::wildcard_matching(matching1,
                                                              pattern1, 0, 0) ==
           1);  // here the pattern matches with given string
    std::cout << "passed" << std::endl;
 
    // 2nd test
    std::cout << "2nd test ";
    std::string matching2 = "baaabab";
    std::string pattern2 = "ba*****ab";
    assert(backtracking::wildcard_matching::wildcard_matching(matching2,
                                                              pattern2, 0, 0) ==
           1);  // here the pattern matches with given string
    std::cout << "passed" << std::endl;
 
    // 3rd test
    std::cout << "3rd test ";
    std::string matching3 = "baaabab";
    std::string pattern3 = "ba*ab";
    assert(backtracking::wildcard_matching::wildcard_matching(matching3,
                                                              pattern3, 0, 0) ==
           1);  // here the pattern matches with given string
    std::cout << "passed" << std::endl;
 
    // 4th test
    std::cout << "4th test ";
    std::string matching4 = "baaabab";
    std::string pattern4 = "a*ab";
    assert(backtracking::wildcard_matching::wildcard_matching(matching4,
                                                              pattern4, 0, 0) ==
           1);  // here the pattern matches with given string
    std::cout << "passed" << std::endl;
 
    // 5th test
    std::cout << "5th test ";
    std::string matching5 = "baaabab";
    std::string pattern5 = "aa?ab";
    assert(backtracking::wildcard_matching::wildcard_matching(matching5,
                                                              pattern5, 0, 0) ==
           1);  // here the pattern matches with given string
    std::cout << "passed" << std::endl;
}

Here is the call graph for this function:

wildcard_matching()

bool backtracking::wildcard_matching::wildcard_matching	(	std::string	s,
		std::string	p,
		uint32_t	pos1,
		uint32_t	pos2 )

                                      {
    uint32_t n = s.length();
    uint32_t m = p.length();
    // matching is successfull if both strings are done
    if (pos1 == n && pos2 == m) {
        return true;
    }
 
    // matching is unsuccessfull if pattern is not finished but matching string
    // is
    if (pos1 != n && pos2 == m) {
        return false;
    }
 
    // all the remaining characters of patterns must be * inorder to match with
    // finished string
    if (pos1 == n && pos2 != m) {
        while (pos2 < m && p[pos2] == '*') {
            pos2++;
        }
 
        return pos2 == m;
    }
 
    // if already calculted for these positions
    if (dpTable[pos1][pos2] != -1) {
        return dpTable[pos1][pos2];
    }
 
    // if the characters are same just go ahead in both the string
    if (s[pos1] == p[pos2]) {
        return dpTable[pos1][pos2] =
                   wildcard_matching(s, p, pos1 + 1, pos2 + 1);
    }
 
    else {
        // can only single character
        if (p[pos2] == '?') {
            return dpTable[pos1][pos2] =
                       wildcard_matching(s, p, pos1 + 1, pos2 + 1);
        }
        // have choice either to match one or more charcters
        else if (p[pos2] == '*') {
            return dpTable[pos1][pos2] =
                       wildcard_matching(s, p, pos1, pos2 + 1) ||
                       wildcard_matching(s, p, pos1 + 1, pos2);
        }
        // not possible to match
        else {
            return dpTable[pos1][pos2] = 0;
        }
    }
}

Variable Documentation

dpTable

std::vector< std::vector< int64_t > > backtracking::wildcard_matching::dpTable(1000, std::vector< int64_t >(1000, -1))	(	1000	,
		std::vector< int64_t >	1000, -1 )

The main function implements if pattern can be matched with given string.

Parameters

s	is the given matching string
p	is the given pattern
pos1	is the starting index
pos2	is the last index

Returns

1 if pattern matches with matching string otherwise 0