Memory issues with Find Strings Problem on InterviewStreet

Here is the code I wrote for the problem at http://www.interviewstreet.com/recruit/challenges/solve/view/4e1491425cf10/4efa210eb70ac where we need to to print the substring at a particular index from the lexicographicaly-sorted union of sets of substrings of the given set of strings...

import itertools
N = int(raw_input())
S = set()
for n in xrange(N):
    W = raw_input()
    L = len(W)
    for l in xrange(1,L+1):
        S=S.union(set(itertools.combinations(W, l)))
        print set(itertools.combinations(W, l))
print S
M = int(raw_input())
S = sorted(list(S))
print S
for m in xrange(M):
    Q = int(raw_input())
    try:
        print "".join(S[Q-1])
    except:
        print "INVALID"

but it gives me a Memory Error meaning that my code takes up more than 256Mb during execution.

I think the culprit is S=S.union(set(itertools.combinations(W, l))), but can't really think of a more efficient method for harvesting a unique set of substrings from the given set of strings...

Can you suggest an optimal alternative?

To successfully pass all test cases you need to implement something more sophisticated like suffix tree. That will allow you to solve this task in O(n) time using O(n) space.

StackExchange Code Review Q#7773, answer score: 4