samedi 1 avril 2017

Wildcard Pattern Matching fails for some cases

You are given a string pattern which consists of characters 'a' to 'z' and exactly one asterisk character ('*') behaving as a wildcard. The wildcard matches zero or more arbitrary characters. The wildcard might be at the front, back, or in the middle of the pattern string.

Given an integer N, followed by N strings. Your task is to find which of these strings match with the pattern.

Example input:

pl*
3
play
pluck
prune

Example output:

play
pluck

Here's my code. The approach is to find where the position of the asterisk in the pattern string, and compare the substring of pattern before the asterisk with the first # characters of the testing string, and also the substring of pattern after the asterisk with the last # characters of the testing string.

It runs almost perfectly, but there is one test case that outputs the wrong answer. I already thought about some cases but I can't find the mistake. Can you help me find the mistake?

#include <iostream>
#include <string>
using namespace std;

int main(){
    string pattern;
    cin >> pattern;
    int patternLen = pattern.length();
    int asterPos = pattern.find('*');

    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        string temp;
        cin >> temp;
        int tempLen = temp.length();

        bool verdict;
        if (tempLen >= patternLen - asterPos - 1) {
            verdict = (temp.substr(0, asterPos) == pattern.substr(0, asterPos)) && (temp.substr(tempLen - patternLen + asterPos + 1) == pattern.substr(asterPos + 1));
        } else {
            verdict = false;
        }

        if (verdict) {
            cout << temp << '\n';
        }
    }
    return 0;
}

Aucun commentaire:

Enregistrer un commentaire