Member Avatar for SAM2012

I am new to this forum. I need help in defining the same kind of function according to my requirements. as http://www.codeproject.com/Articles/1088/Wildcard-string-compare-globbing I hope, I 'll get good response.

Words are strings which are separated by dots. Two additional characters are also valid i.e:The *, which matches 1 word and the #, which matches 0..N words Example: *.stock.# matches the routing keys usd.stock and eur.stock.dsf but not stock.nasdaq.


Your help would be highly appreciated.
Sam

  • 2 Contributors
  • 1 Reply
  • 220 Views
  • 9 Hours Discussion Span
  • Latest Post Latest Post by deceptikon

Dani AI

Generated

Brief summary and approach (building on and ): the real difficulty is the # token because it can absorb a variable number of dot-separated words while later pattern tokens still must line up. A robust solution is an iterative two-pointer loop over pattern-words and key-words that remembers the last # seen and, when a literal match fails, increments how many words that # absorbs (backtracking only to the last #). That yields a simple, efficient matcher without deep recursion.

Key ideas and complexity: split both strings on . into token vectors; iterate with indices i (pattern) and j (key); on * advance both; on literal compare and advance; on # record positions and advance only the pattern pointer; on mismatch, if a # was seen, advance its match by one and resume. Time is O(m+n) in typical use (with linear backtracking), memory O(m+n) for the splits. It is recommended to collapse consecutive # tokens beforehand (they are redundant) and to decide how to treat empty segments from consecutive dots.

#include <string>
#include <vector>
#include <sstream>

static std::vector<std::string> split(const std::string& s, char delim='.') {
    std::vector<std::string> out; std::string t; std::istringstream iss(s);
    while (std::getline(iss, t, delim)) out.push_back(t);
    return out;
}

bool matchRouting(const std::string& pattern, const std::string& key) {
    auto p = split(pattern), k = split(key);
    int i = 0, j = 0, lastHash = -1, lastHashMatch = -1;
    while (j < (int)k.size()) {
        if (i < (int)p.size()) {
            if (p[i] == "#") { lastHash = i++; lastHashMatch = j; continue; }
            if (p[i] == "*" || p[i] == k[j]) { ++i; ++j; continue; }
        }
        if (lastHash != -1) { ++lastHashMatch; j = lastHashMatch; i = lastHash + 1; continue; }
        return false;
    }
    while (i < (int)p.size() && p[i] == "#") ++i;
    return i == (int)p.size();
}

Troubleshooting and tips: normalize case if matching should be case-insensitive; decide whether empty tokens from .. are valid (current code treats them as tokens); add a short pre-pass to collapse multiple # into one. Use unit tests that include patterns where # appears at start, middle, and end, and patterns with literal words after # to validate backtracking.

Member Avatar for deceptikon

The only problem I see is processing the # wildcard. Other than that it's a simple matter of grabbing a word from both the pattern and the source string, then either checking them for equality or not depending on if the pattern word is a * wildcard.

Processing a # wildcard is kind of tricky if you also want to check literals beyond it. So if "#.dsf" should match "eur.stock.dsf" but not "stock.nasdaq", the algorithm needs to consider how many pattern words are remaining and not match too much when processing a # wildcard.

So maybe something like this pseudocode:

WHILE more pwords AND more swords DO
    IF pword = "#" THEN
        -- Get the next non-# pattern word
        NEXT pword WHILE pword <> "#"

        IF NOT more pwords THEN
            -- # is the last word in the pattern, so it matches everything
            RETURN true
        ELSE
            remaining := COUNT pwords

            -- Match everything up to the first remaining pattern word
            WHILE remaining > 0 AND more swords DO
                DECREMENT remaining
            LOOP

            IF remaining = 0 THEN
                -- Insufficient words in the source to match remaining pattern words
                RETURN false
            ENDIF
        ENDIF
    ELSE
        IF pword <> "*" AND sword <> pword THEN
            -- The source word doesn't match a literal pattern word
            RETURN false
        ENDIF
    ENDIF
LOOP

RETURN NOT more pwords OR more swords
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.