[algospot][DP] Wildcard : https://algospot.com/judge/problem/read/WILDCARD

WILDCARD.cpp

#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <iostream>

#define SIZE 101

using namespace std;

vector<vector<int>> dp;
string pattern;
string s;
int pSize = pattern.size();
int sSize = s.size();

/*
 * 시간복잡도 : O(|pattern||s|)
 */
int solve(int pInd, int sInd) {
	int& ret = dp[pInd][sInd];
	if (ret != -1) return ret;
	ret = false;

	if (pSize == pInd && sSize == sInd) return true;
	if (pSize < pInd || sSize < sInd) return false;

	if (pattern[pInd] == '*') {
		for (int i = 0; i <= sSize - sInd; i++) {
			ret |= solve(pInd + 1, sInd + i);
		}
	}
	else if (pattern[pInd] == '?') {
		return ret = solve(pInd + 1, sInd + 1);
	}
	else {
		if (pattern[pInd] != s[sInd])
			return ret = false;
		return ret = solve(pInd + 1, sInd + 1);
	}
	return ret;
}

int main() {
	int C;
	cin >> C;

	while (C--) {
		cin >> pattern;

		pSize = pattern.size();
		

		int N;
		cin >> N;

		set<string> answerSet;
		while (N--) {
			cin >> s;
			dp = vector<vector<int>>(SIZE, vector<int>(SIZE, -1));
			sSize = s.size();
			if (solve(0, 0) > 0) {
				answerSet.insert(s);
			}
		}
		
		for (set<string>::iterator it = answerSet.begin(); it != answerSet.end(); it++) {
			cout << *it << endl;
		}
	}
	return 0;
}