Finding a non-substring [Solution]

The puzzle is here.

In brief, find shortest string which is not a substring of given string.

Solution

---

This will be short too.

Construct the suffix tree of given string, using say a NULL marker for non-existent branches. We can do the marking since the alphabet $\Sigma$ is known.

Now, we can find the smallest depth location where there are no branches. That location gives us a shortest string which is not a substring of the given string.

Suffix trees can be constructed and traversed in $O(n)$ time ($|\Sigma|$ is considered $O(1)$).