The Kleene stars (the * wildcard character for regular expressions) make this difficult. We can’t just gobble up all the wildcard matching characters, otherwise subsequent matches might not work. One way to solve this is by recursing every possibility, so if we have p=“.*abc” and s=“xyzabcabc” then we call our match function with offsets match(s,p,0,2) then match(s,p,1,2) then match(s,p,2,2), etc.. until we have a complete match for the rest of the string. Note that once we’ve read all of string s then we need to step over any trailing wildcards, which don’t need any characters to match.
We can speed this up by using Dynamic Programming memoization to cache previous results. I have included the code for this below the non-memoized embedded code below.