[알고스팟] Wild Card - 동적 계획

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 

 

와일드 카드(링크)

문자열을 대조해서 찾는데 * 는 모두 대응 되므로 * 의 다음 문자와 일치하는 부분 문자열을 하나씩 잘라가며 찾는다. 메모이제이션을 활용할 때는 저장 공간을 reset 하는 시점을 잘 확인해야 한다.

 

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

// -1: initial state, 0: false, 1: true
int cache[101][101];
string wildCard, fileName;


int findMatch(int w, int f) {
    int& ret = cache[w][f];
    if (ret != -1) return ret;

    // Increase idx until you get to the '*'.
    while ((w < wildCard.size() && f < fileName.size())
            && (wildCard[w] == '?' || wildCard[w] == fileName[f])) {
        w += 1; f += 1;
    }

    // idx is the last index of the wildCard string.
    if (w == wildCard.size()) return ret = (f == fileName.size());

    if (wildCard[w] == '*') {
        // Iterate util idx + skip <= fileName.size() since idx + 1 can be
        // the index after the end of the string.
        for (int skip = 0; f + skip <= fileName.size(); ++ skip) {
            if (findMatch(w + 1, f + skip)) 
                return ret = 1;
        }
    }

    return ret = 0;
}

int main() {
    int C; cin >> C;
    priority_queue<string, vector<string>, greater<string>> answers;
    vector<string> ans;

    while (C-- > 0) {
        cin >> wildCard;

        int n; cin >> n;
        while (n-- > 0) {
            cin >> fileName;
            for (auto& row: cache) for (auto& e: row) e = -1;

            if (findMatch(0, 0)) 
                answers.push(fileName);
        }
        while (!answers.empty()) {
            ans.push_back(answers.top());
            answers.pop();
        }
    }
    
    cout << endl;
    for (const auto& e: ans) cout << e << endl; 

    return 0;
}