5
$\begingroup$

There is a problem.

Given string $text$ containing only letters and string $mask$ containing letters and asterisks (*), where asterisk means substitution of zero or more letters, find all substrings of $text$ that fit $mask$.

There is an example: let's $text=cabccbacbacab$, $mask=\textbf{ab}*\textbf{ba}*\textbf{c}$. The algorithm should give substrings $abccbac$, $abccbacbac$, because $abccbac = \textbf{ab} + cc + \textbf{ba} + \textbf{c}$, $abccbacbac = \textbf{ab} + ccbac + \textbf{ba} + \textbf{c}$.

I have tried to split mask into tokens (for above example $\textbf{ab},\textbf{ba},\textbf{c}$) then find all occurrences of every token in $text$ then make cartesian product of all relevant occurrences and check every token for condition.

Is there more efficient solution for this problem?

$\endgroup$
  • 2
    $\begingroup$ This is a particular case of regular expression matching. $\endgroup$ – Yuval Filmus May 7 '18 at 15:49
8
$\begingroup$

Yes, there is a more efficient algorithm. Your algorithm can take exponential time.

You can check whether there exists any match in $O(nm)$ time, where $n$ is the length of text and $m$ is the length of mask, and find all matches in $O(n^2m)$ time. I'll show two solutions, one using dynamic programming and one using graph search. You can pick whichever you find easier to understand.

I don't know whether you can do even better.

Dynamic programming

Build an array $A[i,j]$, where $A[i,j]$ is true if some prefix of $\text{text}[i..n]$ matches $\text{mask}[j..m]$. There's a recursive formula for $A[i,j]$:

$$\begin{align*} A[i,j] &= \text{True} \qquad &&\text{if } j=m+1\\ A[i,j] &= A[i+1,j+1] \qquad &&\text{if } \text{mask}[j]=\text{text}[i]\\ A[i,j] &= A[i,j+1] \lor \cdots \lor A[n,j+1] \qquad &&\text{if } \text{mask}[j]=*\\ A[i,j] &= \text{False} \qquad &&\text{otherwise} \end{align*}$$

If you fill this in, in the usual way, you get a $O(nm^2)$ time algorithm. If you additionally keep track of $B[i,j] = A[i,j+1] \lor \cdots \lor A[n,j+1]$ and fill in entries in the right order, you get a $O(nm)$ time algorithm.

Once you have filled in the matrix, you can find all substrings of text that match: each entry $A[i,1]$ that is true corresponds to one or more substrings of text that match (the substring starts at index $i$ of text). You can adapt the above algorithm to enumerate all those matching substrings by repeating the above computation once per possible ending place of the match.

There may be even faster methods, using ideas from string matching and/or regular expression matching.

Graph search

Build a directed graph on $nm$ vertices. Each vertex is of the form $\langle i,j \rangle$, which we think of as corresponding to the problem of checking whether some prefix of $\text{text}[i..n]$ matches $\text{mask}[j..m]$. Now add the following edges:

  • Add the edge $\langle i,j \rangle \to \langle i+1,j+1 \rangle$ if mask$[j]$ = text$[i]$.
  • Add the edge $\langle i,j \rangle \to \langle i,j' \rangle$ if mask$[j] = *$ and $j' > j$.

Finally, mark each vertex $\langle i,m+1 \rangle$ as "accepting".

This is a directed acyclic graph; it has no cycles. Now, for each $i$, find all accepting vertices that are reachable by some path starting at the vertex $\langle i,1 \rangle$. If $\langle i',m+1 \rangle$ is reachable from $\langle i,1 \rangle$, that means that the substring text$[i..i'-1]$ matches mask, so you can output this substring. This computation can be done in $O(nm)$ time per starting point using breadth-first search, for a total of $O(n^2m)$ time.

$\endgroup$
  • $\begingroup$ Sorry, my claim about an exponential number of solutions was wrong -- there are only $O(n^2)$ possible substrings of the text, so there can't be more solutions than that! Nevertheless there can be more than $nm$ solutions (simplest case: $text$ consists of $n$ distinct characters and $mask = *$). $\endgroup$ – j_random_hacker May 7 '18 at 19:02
  • $\begingroup$ @j_random_hacker, indeed. You're absolutely right. My previous answer was erroneous, because I missed the requirement to find all matching substrings (I was previously answering how to test whether a match exists or not). See my revised answer for a correction. Maybe you can find a faster algorithm? $\endgroup$ – D.W. May 7 '18 at 19:05
  • $\begingroup$ It might be possible to get (closer to) an output-sensitive algorithm by using the Aho-Corasick algorithm in a first pass to locate all matches of any mask "segment" (maximal wildcard-free substring) in linear time, and then running a variation of your DP on the graph you get by making a vertex for each segment occurrence in the text and an arc between every pair of adjacent occurrences (in the text) of adjacent segments (in the mask). But without further cleverness, I think this can still get unnecessarily bogged down in quadratic time when the mask contains multiple equal segments... $\endgroup$ – j_random_hacker May 7 '18 at 19:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.