와일드카드

알고스팟 문제 : https://algospot.com/judge/problem/read/WILDCARD

algospot.com :: WILDCARD

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 10) 가 주어진다. 각 테스트 케이스의 첫 줄에는 와일드카드 문자열 W 가 주어지며, 그 다음 줄에는 파일명의 수 N (1 <= N <= 50) 이 주어진다. 그 후 N 줄에 하나씩 각 파일명이 주어진다. 파일명은 공백 없이 알파벳 대소문자와 숫자만으로 이루어져 있으며, 와일드카드는 그 외에 * 와 ? 를 가질 수 있다. 모든 문자열의 길이는 1 이상 100 이하이다.

출력

각 테스트 케이스마다 주어진 와일드카드에 매치되는 파일들의 이름을 한 줄에 하나씩 아스키 코드 순서(숫자, 대문자, 소문자 순)대로 출력한다.

 

 

코드(C++) 종만북 참조

 

#include 
#include 
#include 
#include 
using namespace std;
const int MAX = 100 + 1;
int cache[MAX][MAX];
vector s;
string W, S;
int match(int w, int s)
{
int& ret = cache[w][s];
if (ret != -1)
return ret;
while (s < S.size() && w < W.size() && (W[w] == S[s]) || W[w] == '?')
{
++w;
++s;
}

if (w == W.size())
return ret = (s == S.size());
if (W[w] == '*')
for (int skip = 0; skip + s <= S.size(); ++skip)
if (match(w + 1, s + skip))
return ret = 1;
return ret = 0;
}
void init() {
for (int i = 0; i < 101; ++i)
for (int j = 0; j < 101; ++j)
cache[i][j] = -1;
}
int main() {
int C;
cin >> C;
while (C--)
{
W.clear();
cin >> W;
int num;
cin >> num;
for (int i = 0; i < num; ++i)
{
init();
cin >> S;
if (match(0, 0))
s.push_back(S);
S.clear();
}

// sort(s.begin(), s.end()); 알고스팟은 정렬 해줘야함.
for (string n : s)
cout << n << endl;
s.clear();
}
return 0;
}