Determining if match is possible

Question

I have a list of patterns with each pattern containing one or more wildcards. For example:

• abc*
• a*
• *a*z*
• *z

Wildcard (*) matches one or more characters. For example, any input string starting with 'a' would match a pattern a*.

How can I determine if there exists an input string that would match all of the provided patterns?

Answer 1

The language-theoretic answer:

Convert each regexp to a DFA, then use the product construction to take the intersection of their languages. Check whether the resulting DFA accepts any word (i.e., whether its language is non-empty). This might take exponential time in the worst case.

The pragmatic answer:

Every pattern has the form $\alpha \texttt{*} \beta \texttt{*} \gamma$, where $\alpha,\gamma$ are (possibly empty) strings of letters (without wildcards), and where $\beta$ is a (possibly empty) pattern (i.e., a string of letters and wildcards). Let the patterns be $\alpha_i \texttt{*} \beta_i \texttt{*} \gamma_i$ for $i=1,2,\dots,n$. Find a string $A$ so that each $\alpha_i$ is a prefix of $A$; if no such string exists, output "NO" and terminate. Find a string $C$ so that each $\gamma_i$ is a prefix of $C$; if no such string exists, output "NO" and terminate. Find a string $B$ that matches $\texttt{*} \beta_i \texttt{*}$ for each $i$; this can always be done. Finally, output "YES" and the string $ABC$.

This is your exercise, so I'll let you figure out how to find each of $A$, $B$, and $C$ -- it's not hard.