Regular Expression Matching

Given two strings s and p, implement regular expression matching with support for '.' and '*'. A dot . matches any single character, while an asterisk * matches zero or more of the preceding element. The matching must cover the entire input string (not partial).

You are required to determine whether the pattern p matches the entire string s. The dynamic programming recurrence can be summarized by the following formula:

$$ \text{dp}[i][j]=\begin{cases} \text{dp}[i-1][j-1] & \text{if } p[j-1]=s[i-1] \text{ or } p[j-1]='.'\\[8pt] \text{dp}[i][j-2] \;\text{ or }\; \text{dp}[i-1][j] & \text{if } p[j-1]=='*' \;\text{and } (p[j-2]=s[i-1] \text{ or } p[j-2]=='.') \end{cases} $$

Note: Either or both of s and p can be empty.

inputFormat

The input consists of two lines from stdin. The first line contains the string s, and the second line contains the pattern p.

outputFormat

Output a single line to stdout: True if the entire string s matches the pattern p, otherwise output False.

aa
a

False