mickypinata

SIGNAL-DP-ADV-T002: Regular Expression Matching

Dec 4th, 2021
1,203
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int S = 20 + 5;
  5. const int P = 30 + 5;
  6.  
  7. string str, pat;
  8. bool dp[S][P], isMulti[P];
  9.  
  10. bool solution(string &s, string &pat){
  11.     s = '\0' + s;
  12.     string p(1, '\0');
  13.     for(int j = 0; j < pat.size(); ++j){
  14.         char c = pat[j];
  15.         if(c == '*'){
  16.             isMulti[(int)p.size() - 1] = true;
  17.             continue;
  18.         }
  19.         p.push_back(c);
  20.     }
  21.     int lenS = (int)s.size() - 1;
  22.     int lenP = (int)p.size() - 1;
  23.     dp[0][0] = true;
  24.     for(int i = 0; i <= lenS; ++i){
  25.         for(int j = 1; j <= lenP; ++j){
  26.             bool ans = false;
  27.             if(isMulti[j]){
  28.                 ans |= dp[i][j - 1];
  29.             }
  30.             if(s[i] == p[j] || p[j] == '.'){
  31.                 if(isMulti[j]){
  32.                     ans |= dp[i - 1][j];
  33.                 }
  34.                 ans |= dp[i - 1][j - 1];
  35.             }
  36.             dp[i][j] = ans;
  37.         }
  38.     }
  39.     return dp[lenS][lenP];
  40. }
  41.  
  42. int main(){
  43.  
  44.     cin >> str >> pat;
  45.     printf("%d", solution(str, pat));
  46.  
  47.     return 0;
  48. }
  49.  
RAW Paste Data