Find the shortest string that is not a sub-string of a set of strings Alphabet: abc

Sample input:


abc
cba
aabbcc
aaabbbccc
caac


Sample good outputs: acb, cab, cac and others, since they are not substrings of any other, and because all strings of length 1 and 2 are present.

Sample bad outputs:


aab since it is a substring of 3)
aaaa because it is not minimal: we have other solutions with 3 characters only


Questions:


What are the best ways to solve it?
Does the problem have a well known coined name?
What is the complexity of the calculation in terms of the input size (number of strings N and maximum string length M)?
What is the average asymptotic size of the output considering random uniformly distributed inputs?


Related questions:


Algorithm Request: &quot;Shortest non-existing substring over given alphabet&quot; seems to be the case for a single input string. If we can find a trivial reduction we can close as a duplicate.


Applications:


for file uploads, browsers use the enctype='multipart/form-data' encoding. This encoding can send several files in a single HTTP request. Files are sent directly without character encoding, so to separate the files, the browser has to find a string that is not contained in any of the files. I'd like to know how that can be done optimally. See also: https://stackoverflow.com/questions/4526273/what-does-enctype-multipart-form-data-mean/28380690#28380690
apparently this has some interest for bioinformatics, although I know nothing about that domain: https://biology.stackexchange.com/questions/3064/shortest-strings-not-present-in-the-human-genome . There has been some discussion on that question, but the answers there are more heuristic than algorithmic.
Here's one possible solution, similar to the linked question: Algorithm Request: “Shortest non-existing substring over given alphabet”

Use a sliding window over each input string to build your trie. 


For n=1 to n=max(length(s)) where s is an input string, do:
For each s, construct window of size n, slide window over s adding each window (substring of size n) to the trie, then
Visit each parent of the leaf set of the trie. If there exists a parent node whose set of child nodes is smaller than the size of the alphabet, then you can form your desired string from this parent by appending a character from the alphabet that does not result in a string identical to one of the leaf nodes
If no such parent node exists, continue to next larger n