A hangman variation: determining a string by guessing substrings contained in it I came up with this Hangman variation, where you must figure out the hidden word by asking whether a string is a substring of this word. E.g. if the hidden word is "abracadabra" and I guess "cad" I will get a positive result, and if I guess "arb" I get a negative result. When I guess the word I win.

My first question is if anyone knows whether this problem is known and has been solved before?

I came up with an algorithm, which seems to operate in sub-quadratic* number of guesses (by input length) by iteratively generating graphs of 1..n length substrings. In this graph the nodes are the positively guessed k-length substrings and the edges connect to possible continuations. New k+1-length guesses are generated by appending to these possible continuations, giving one new guess per edge. Once the graph becomes a loop you can try appending all nodes in order, until you solve the word. Here's a Java implementation.

My second question is if anyone can help me figure out the time complexity of this algorithm? As there can be at most n graphs, with n being the input length, each having up to n^2 edges, then multiplied by the n time needed for the substring function gives an upper bound of O(n^4). This is assuming a constant-sized alphabet. However, I doubt this is the tightest upper bound possible.

*experimentally, with a constant-size alphabet
This problem can be solved with O(n * s) queries, where n is the input length and s is the alphabet size. First, determine some single character substring by trying all possibilities. Then extend that into a length 2 substring by trying to append characters to it. Continue extending the string by appending until it's not possible anymore. If it's not possible to append anymore and the length is not n, do the same strategy but prepending. In this way you reach the length n substring in n steps that each take at most s queries.