알고스팟 - WILDCARD

https://algospot.com/judge/problem/read/WILDCARD

패턴 문자열 $p$와 비교 대상 $s$을 한자리씩 비교한다. 이 때, 비교하는 위치는 서로 다를 수 있다.
비교하고자하는 $p$의 위치를 $i$, $s$의 위치를 $j$ 라 하면, 각 자리의 비교 함수 $f(i, j)$의 진행은 아래와 같이 조건 분기가 가능하다.

- $p_i$와 $s_j$가 같거나 $p_i$가 ?인 경우, $f(i+1, j+1)$ 을 확인한다.
- $p_i$가 *인 경우, *가 $[s_j, s_k]$ ($k$는 문자열 $s$의 끝 위치) 까지의 범위를 대응시킬 수 있다. 하나씩 확인해본다.
- $p_i$와 $s_j$가 다른 경우, 패턴을 찾을 수 없다.
- 종료조건 : 패턴에 있는 모든 문자에 대해 검색이 끝났을 때, 비교 문자열 역시 검색을 마친(끝 위치에 있는) 경우라면 패턴에 부합한다는 뜻이다.

#include <bits/stdc++.h>
using namespace std;

#define INF 987654321

char s[101], p[101];
int slen, plen;

int dp[101][101];

int wild(int i, int j){
    if(i >= plen) return j==slen;
        
    int& r = dp[i][j];
    if(r != -1) return r;
    
    if(p[i]=='*'){
        for(int k=j; k<=slen; ++k)
            if( wild(i+1, k) == 1 ) return r = true;
    }
    
    if(p[i]==s[j] || p[i]=='?')
        return r = wild(i+1, j+1);
    
    return r = false;
}

int main(){
    int N, T;
    scanf("%d ", &T);
    while(T--){
        scanf("%s %d ", p, &N);
        plen = strlen(p);
        vector<string> v;
        for(int i=0; i<N; ++i){
            scanf("%s ", s);
            memset(dp, -1, sizeof(dp));
            slen = strlen(s);
            if( wild(0, 0) == 1 ) v.push_back(s);
        }
        sort(v.begin(), v.end());
        for(int i=0; i<v.size(); ++i) puts(v[i].c_str());
    }
    return 0;
}

책을 보니까 *와 일치하는 경우를 아래와 같이 바꿔도 된다.

if(p[i]=='*'){
    return r = (wild(i+1, j) == 1 || wild(i, j+1) == 1);
}