AOJ - WILDCARD

AOJ - WILDCARD

$O(n^2)$ $dp$로 문제를 해결한다.

문자열 $S,\,T$가 있을 때,

$\quad dp_{i,\,j}=S \text{ 와 } T$가 앞에서부터 $S_i$ 와 $T_j$ 까지 따졌을 때 매칭이 될 수 있는지 여부라고 하자.

$S_i=T_j$ 이거나 $S_{i}=$ ? 라면 $dp_{i,j}$ 는 $dp_{i-1,\,j-1}$ 이 참이라면 참이다.

만약 $S_i=$ * 이라면 $T_j$를 하나 없애거나 넘기지 않거나 선택지가 생기고,

• 하나 없앨 때 $dp_{i,\,j-1}$
• 없애지 않고 넘길 때 $dp_{i-1,\,j}$

둘 중 참이 하나라도 있으면 참이다.

가장 처음에 $dp_{0,\,0}$ 같은 경우는 1이고 만약 $S$의 가장 앞에 *가 붙어있는 경우 $dp_{1,\,j}$ 들이 모두 참이므로 잘 처리해주고 시작한다.

void solve() {  
   string a;  
   cin >> a;  
   int n;  
   cin >> n;  
   vs arr(n);  
   fv(arr);  
   a = " " + a;  
   vs ans;  
   for (string b: arr) {  
      n = sz(a) - 1;  
      int m = sz(b);  
      vvi dp(n + 1, vi(m + 1));  
      b = " " + b;  
      dp[0][0] = 1;  
  
      if (a[1] == '*') {  
         for (int j = 0; j <= m; j++)dp[1][j] = 1;  
      }  
  
      for (int i = 1; i <= n; i++) {  
         for (int j = 1; j <= m; j++) {  
            if (a[i] == b[j] || a[i] == '?') {  
               // 2, 1  
               // 1, 0               dp[i][j] |= dp[i - 1][j - 1];  
            }  
  
            if (a[i] == '*') {  
               dp[i][j] |= dp[i][j - 1] | dp[i - 1][j];  
            }  
         }  
      }  
      if (dp[n][m]) ans.pb(b.substr(1));  
   }  
   sort(all(ans));  
   for (string b: ans) cout << b << endl;  
}