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)$).
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)$).
No comments:
Post a Comment