AOJ - WILDCARD

O(n2)O(n^2) dpdp로 문제를 해결한다.

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

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

Si=TjS_i=T_j 이거나 Si=S_{i}= ? 라면 dpi,jdp_{i,j} 는 dpi−1, j−1dp_{i-1,\,j-1} 이 참이라면 참이다.

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

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

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

가장 처음에 dp0, 0dp_{0,\,0} 같은 경우는 1이고 만약 SS의 가장 앞에 *가 붙어있는 경우 dp1, jdp_{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;  
}

Comments

You may also enjoy