current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 3 down vote favorite
1

I'm looking for an (efficient) algorithm to solve the following problem:

Given a string $S$ and a set of characters $M$, find the shortest string composed only of characters in $M$ that is not contained in $S$.

Try as I might, I can't seem to map this problem to any of the standard CS string problems.

share|improve this question
 
What specifically have you tried? –  Raphael♦ Feb 22 at 9:25
 
I don't know what you mean by "standard CS string problems", but modern stringology uses suffix trees/arrays as a basic primitive, since they can be constructed in linear time using linear space. (If you are using suffix arrays, you'll need the lca array too.) Once you know that, you should be able to solve the problem in linear time. (As a further hint, if there is a character in $M$ that is not in $S$, then a one-character string is a valid answer to the question.) –  Pseudonym Feb 23 at 10:12
 
Incidentally, compare with this question on SE. stackoverflow.com/questions/12607512/… –  Pseudonym Feb 23 at 13:15
add comment

3 Answers

up vote 5 down vote accepted

Here is the clean presentation (after going in circles around it).

First you consider all substrings of S that are in M*. From that you build a trie, which may be understood as a tree structured FA that recognizes these substrings. You build it so that you complete first the transitions of nodes that are closest to the root. As soon as you have a node from which there is no arc for a given character in M, you have your answer which is the string associated with that node concatenated with the missing character. Complexity is $O(n^2)$ where $n$ is the length of the string S, because that is the maximum number of characters you may have to consider while building the trie.

Note regarding complexity: In the trie construction you have to consider only the longest substring in $M^*$ starting at each position in $S$, since shorter ones are automatically taken care of. Each state thus created is an accepting state recognizing one substring. There are at most $n$ substrings in $M^*$, each having at most $n$ characters. Each is considered in constant time.

share|improve this answer
 
Looks like that might work indeed. Complexity should be dominated by a term linear in the length of the string. Sounds mighty hard to implement though... –  user232362636 Feb 21 at 19:11
 
Not too hard. Everything is easy and fast, except the building of the initial automaton. This requires a bit of thinking if you want to do it fast. –  babou Feb 21 at 19:13
 
I definitely like the idea (sorry, can't upvote yet, requires 15 reputation). I'd still like to hear alternative approaches, though. –  user232362636 Feb 21 at 19:20
 
Actually, the building of the initial FA isn't the problem. It's a simple matter build a FA with $|\;S\;|$ states that will accept all the substrings of $S$. The problem is that you might wind up with a nondeterministic FA. There's a simple construction to go from a deterministic FA to a FA that accepts the complement of the first one, but I don't know of any easy way to do that before first making the FA deterministic. Unfortunately a NFA with $n$ states might require $O(2^n)$ states in its deterministic equivalent, which kills your complexity. –  Rick Decker Feb 21 at 19:24
 
Uuhh... that's not what I want then. –  user232362636 Feb 21 at 19:29
show 8 more comments
up vote 2 down vote

Let $n = |w|$ and $m = |\Sigma|$, where $w$ is the input string and $\Sigma$ is the input alphabet. There are $n - k + 1$ substrings of $w$ of length $k$, and $m^k$ strings over $\Sigma$ of length $k$. If $n - k + 1 < m^k$ then, by the pigeonhole principle, there must be a string over $\Sigma$ of length $k$ that is not a substring of $w$.

There are on the order of $m^i$ strings of length less than $i$ over $\Sigma$. Determining whether an arbitrary string is a substring of $w$ can be done in time $n$. Thus we have, at most, $nm^i$ work to do, where $i = k + 1$ in the worst case. We can extrapolate from the inequality that $n < m^k$, so $k > \log_m n$; so $k = 1 + \log_m n$ always works. Note: if we can rule out $k = 1$, we can go even further and let $k = \log_m n$.

Taken altogether, this means that the total amount of work that the naïve method (enumerate strings in lexicographic order, and check the input for each string over $\Sigma^*$ until you find one that's missing) would never do more than $O(n^2m^2)$ (*fixed an algebraic mistake; had $O(n^3m)$ previously, but should have been $O(n^2m^2)$) work in the worst case, although this bound may not be tight. Note that if we rule out $k = 1$ and take $k = \log_m n$, we lose an $n$ and get $O(n^2m)$.

share|improve this answer
 
Hmm... if the size of the dictionary (example) is 1 MB and $m = 26$, $O(n^3m)$ sounds a bit less than practical, though of course the actual work might be less in that case :) –  user232362636 Feb 21 at 19:40
 
@user232362636 Agreed... it's worth pointing out that the number of words of length less than $i$ is really closer to $\frac{m^i}{m-1} + m$, so the $m$ term ends up going away, and we're left with something more like $O(n^3)$. Still, it's always nice when you can not only clearly state an effective computation for something, but that computation turns out to be a relatively straightforward polynomial. –  Patrick87♦ Feb 21 at 19:45
 
@user232362636 Take another look at my post; I fixed an algebraic mistake, so the complexity from the original argument should have been $O(n^2m^2)$ originally. I also realized that in most cases ($n$ greater than $m$, particularly) we can always choose a smaller value for $k$, reducing the overall complexity to $O(n^2m)$; the real answer might even be something closer to $O(n^2)$, based on the above comment (which still applies). It might be a fun exercise for you to implement brute-force search to see if this algorithm or babou's performs better. –  Patrick87♦ Feb 21 at 20:41
 
Thanks, that's exactly what I'll do (first I have to implement babou's solution though, which will be more difficult than yours though it feels cleaner). –  user232362636 Feb 21 at 21:56
add comment
up vote 0 down vote

Here is another approach that is conceptually simple (you are asking for "standard string problems").

  1. Construct an NFA $A$ for $M^*$ (two states).
  2. Construct an NFA $B$ for $\{ w \mid vwx = S; v,w,x \in \Sigma^* \}$ ($n+2$ states).
  3. Compute $\overline{B}$.
  4. Compute $\overline{B} \cap A$.
  5. Find a shortest path from the starting state to a final state (breadth-first search). The traversed edges make up your solution.

Per se, the time for 3. might be huge (and then also 4.) since inverting NFA takes exponential time in the worst case.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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