정규 표현식 (Regular Expression, Regex)

# Thompson NFA 기반 regex 매칭
import sys
class State:
  def __init__(self):
      self.c = None; self.out = None; self.out1 = None
class NFA:
  def __init__(self, s, a): self.start = s; self.accept = a
def to_nfa(post):
  stk = []
  for c in post:
      if c == '.':
          b, a = stk.pop(), stk.pop()
          a.accept.out = b.start; a.accept.c = None
          stk.append(NFA(a.start, b.accept))
      elif c == '|':
          b, a = stk.pop(), stk.pop()
          s, acc = State(), State()
          s.out = a.start; s.out1 = b.start
          a.accept.out = acc; b.accept.out = acc
          stk.append(NFA(s, acc))
      elif c == '*':
          a = stk.pop(); s, acc = State(), State()
          s.out = a.start; s.out1 = acc
          a.accept.out = a.start; a.accept.out1 = acc
          stk.append(NFA(s, acc))
      else:
          s, acc = State(), State(); s.c = c; s.out = acc
          stk.append(NFA(s, acc))
  return stk[0]
def eps(states):
  stk = list(states)
  while stk:
      s = stk.pop()
      if s.c is None:
          if s.out and s.out not in states: states.add(s.out); stk.append(s.out)
          if s.out1 and s.out1 not in states: states.add(s.out1); stk.append(s.out1)
  return states
def match(nfa, text):
  states = eps({nfa.start})
  for ch in text:
      nxt = set()
      for s in states:
          if s.c == ch or s.c == '.': nxt.add(s.out)
      states = eps(nxt)
  return nfa.accept in states
prec = {'*':3, '.':2, '|':1}
def postfix(re):
  out, stk, i, p = [], [], 0, ''
  while i < len(re):
      c = re[i]
      if c == '(':
          if p and p not in '(|': stk.append('.')
          stk.append(c)
      elif c == ')':
          while stk and stk[-1] != '(': out.append(stk.pop())
          stk.pop()
      elif c in '*|':
          if c == '|' and out and out[-1] in '(|': out.append('')
          while stk and stk[-1] != '(' and prec.get(stk[-1],0) >= prec.get(c,0):
              out.append(stk.pop())
          stk.append(c)
      else:
          if p and p not in '(|*': stk.append('.')
          out.append(c)
      p = c; i += 1
  while stk: out.append(stk.pop())
  return ''.join(out)
re = sys.stdin.readline().strip()
print(1 if match(to_nfa(postfix(re)), sys.stdin.readline().strip()) else 0)

// Regex 매칭 (백트래킹, 문자/./*/|/()/연결)
import java.io.*;
public class Main {
  static boolean match(String s, int si, String p, int pi) {
      if (pi == p.length()) return si == s.length();
      boolean star = pi+1 < p.length() && p.charAt(pi+1) == '*';
      if (star) {
          if (match(s, si, p, pi+2)) return true;
          while (si < s.length() && (p.charAt(pi)=='.' || s.charAt(si)==p.charAt(pi))) {
              if (match(s, si+1, p, pi+2)) return true;
              si++;
          }
          return false;
      }
      if (si < s.length() && (p.charAt(pi)=='.' || s.charAt(si)==p.charAt(pi)))
          return match(s, si+1, p, pi+1);
      return false;
  }
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      System.out.println(match(br.readLine(), 0, br.readLine(), 0) ? 1 : 0);
  }
}