A hangman variation: determining a string by guessing substrings contained in it

Question

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