You can solve this in polynomial time by using a dynamic programming algorithm. The idea is to answer queries of the following form:
Can you match the last m characters of the string using the last n characters of the regular expression?
The idea is to use a recursive algorithm, then either memoize the results or use dynamic programming to cache the results. The recursive algorithm works as follows:
- If the regular expression is empty, it only matches the empty string.
- If the regular expression's second character isn't *, then the regular expression matches the string iff the first character of the string matches the regex and the rest of the string matches the rest of the regex.
- If the regular expression's second character is *, then the regular expression matches the string iff one of the following is true:
- The first character of the regular expression matches the first character of the string, and the same regular expression matches the remainder of the string.
- The first character of the regular expression matches the first character of the string, and the regular expression with the *'ed expression removed matches the rest of the string.
- The first character of the regular expression doesn't match the first character of the string, but the regex formed by removing the *'ed expression matches the string.
Each of these cases makes a recursive call where either the string or the regex is shorter and does O(1) work aside from the recursive calls. Since there are only Θ(mn) possible subproblems (one for each combination of a suffix of the regex and a suffix of the original string), using memoization this problem can be solved in Θ(mn) time.
Hope this helps!