Regular Expression Matching

You are given two strings s and p. The pattern p may contain the special character . which matches any single character, and the character * which matches zero or more of the preceding element. Your task is to determine if the pattern p matches the entire string s using the following rules:

• . Matches any single character.
• * Matches zero or more of the preceding element.

Note: The matching should cover the entire input string (not partial). You are expected to use dynamic programming to solve this problem.

The regular expression matching follows the typical precedence rules. For example, the pattern a* means zero or more occurrences of a and .* means zero or more of any character.

The problem can be mathematically formulated using a DP approach as follows. Let \(dp[i][j]\) be a boolean value representing whether the substring \(s[0 \ldots i-1]\) matches the pattern \(p[0 \ldots j-1]\). The recurrence relation can be derived based on whether the current character in the pattern is a regular character, a dot (\( . \)), or a star (\( * \)).

inputFormat

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

outputFormat

Output a single line to standard output containing either 'True' or 'False' (without quotes), indicating whether the pattern p matches the entire string s.## sample

aa
a

False