def test(t): t += '$' root = {} for i in [[xrange]](len(t)): cur = root for c in t[i:]: cur[c] = {} cur = cur[c]