[알고스팟] 와일드카드 ID: WILDCARD

문제 링크

algospot.com :: WILDCARD

와일드카드란 어떤 문자도 가능한 만능 문자로 *는 0글자 이상의 문자로 대체 가능하고, ?는 어떠한 문자 (1글자)로 대체될 수 있습니다.

예를 들어 b*a 는 bba, banana, ba와 같은 문자들로 대응될 수 있으며 b?a는 bba, baa, bca 로 대응 될 수 있지만 bbaa, ba와 같은 문자로 대응될 수 없습니다.

특정 와일드카드를 0개 이상 포함된 문자열이 주어지고, 대응 후보 문자열이 여러개 주어졌을 때, 대응될 수 있는 문자열을 찾기 위해 2가지 규칙을 적용해야 합니다.

와일드 카드가 포함된 문자열 w_str 과 비교하는 문자열 str은 

1. 현재 비교하는 문자 w_str[i] 가 와일드 카드가 아닌경우

두 문자열을 비교하여 w_str[i] == str[j] 면 다음 문자열을 비교

다르면 대응될 수 없으므로 비교작업을 끝냄.

2. 현재 비교하는 문자가 와일드 카드 * 또는 ? 인 경우

   1) * 인 경우

* 가 빈 문자열이거나 or str[j: str.length()-1] 범위의 연속된 부분 문자열이 되거나

w_str[i] 를 빈 문자열로 취급하거나
   i+=1, j 고정

w_str[i] 를 str[j] 문자열의 일부로 취급하거나
   i 고정, j를 str 문자열 길이까지 반복

   2) ? 인 경우

 w_str[i] == str[j] 인 상태와 동일하게 취급
   i+=1, j +=1

 

동적 계획법으로 풀었습니다. dp[i][j]는 w_str[0]~w_str[i]와 str[0]~str[j]가 대응되는지 여부를 저장합니다.

입력크기가 작아 단순탐색으로도 풀린다고 하네요.

#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <memory.h>
#include <string.h>
#include <algorithm>

using namespace std; 


string w_str;
string str[51];
int dp[102][102]; // w_str[i]와 str[j]가 대응 되는가 1, 안되는가 0
int n;
int w_len, str_len;
bool recv(int i, int j, int idx) {
	if (i == w_len) { // 와일드 문자열이 끝까지 비교된 경우
		if (j == str_len) { // 비교 문자열도 끝까지 비교되면 대응 가능
			return true;
		}
		return false;
	}

	int& ret = dp[i][j];
	if (~ret) return ret;
	ret = 0;
	
	if (w_str[i] == str[idx][j]) { // 규칙 1 . 같은 경우
		ret = recv(i + 1, j + 1, idx);
	}
	else {
		if (w_str[i] == '*') { // 규칙 2-1
			ret |= recv(i + 1, j, idx); // i+=1, j 고정
			if (!ret) {
				while (j <= str_len) {
					ret |= recv(i, j, idx); // i고정, j+=1
					j += 1;
				}
			}
		}
		else if (w_str[i] == '?') { // 규칙 2-2
			ret = recv(i + 1, j + 1, idx);
		}
	}
	// 규칙 1. 다른 경우 그대로 false return
	return ret;
}
void solve() {
	vector<string> ans;
	cin >> w_str;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> str[i];
	}
	w_len = w_str.length();
	
	for (int i = 0; i < n; i++) {
		memset(dp, -1, sizeof(dp));
		str_len = str[i].length();
		if (recv(0, 0, i)) {
			ans.push_back(str[i]);
		}
	}
	sort(ans.begin(), ans.end());
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << "\n";
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	for (; t--;) {
		solve();
	}
}

 

추가된 예제 ( 알고스팟 댓글에 있는것 가져옴 )

6
he?p
3
help
heap
helpp
*p*
3
help
papa
hello
*bb*
1
babbbc
t*l?*o*r?ng*s
3
thelordoftherings
tlorngs
tllorrngs
******a
2
aaaaaaaaaab
abcdea
a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a
2
ahfjsdhfjkdshfkjdshfkdsaojajfjaljaflkajflkdsaljflkaflsaffasfa54656454aafasfsdafsaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbb