Revision history [back]

Here is a function that compute the set of subwords (no repetition)

def subwords(w, W=None):
    r"""
    Return the subwords of ``w`` without repetition.

    INPUT:

    - ``w`` - a finite word (or string or list)

    - ``W`` - an optional parent

    EXAMPLES::

        sage: subwords('aab')
        ['', 'a', 'aa', 'ab', 'ab', 'b']
        sage: subwords('aba')
        ['', 'a', 'b', 'ab', 'ba', 'aa', 'aba']

        sage: subwords(Word('abc'))
        [word: , word: a, word: b, word: ab, word: c, word: bc, word: ac, word: abc]
    """
    if W is None:
        try:
            W = w.parent()
        except AttributeError:
            W = type(w)

    T = {}
    L = [W()]
    for a in w:
        todo = [(W(),T)] 
        while todo:
            cw, t = todo.pop()
            todo.extend((cw+W(b),tt) for b,tt in t.items())
            if a not in t:
                t[a] = {}
                L.append(cw + W(a))

    return L

Here is a function that compute the set of subwords (no repetition)

def subwords(w, W=None):
    r"""
    Return the subwords of ``w`` without repetition.

    INPUT:

    - ``w`` - a finite word (or string or list)

    - ``W`` - an optional parent

    EXAMPLES::

        sage: subwords('aab')
        ['', 'a', 'aa', 'b', 'ab', 'ab', 'b']
'aab']
        sage: subwords('aba')
        ['', 'a', 'b', 'ab', 'ba', 'aa', 'aba']
        sage: subwords('aaa')
        ['', 'a', 'aa', 'aaa']

        sage: subwords(Word('abc'))
        [word: , word: a, word: b, word: ab, word: c, word: bc, word: ac, word: abc]
    """
    if W is None:
        try:
            W = w.parent()
        except AttributeError:
            W = type(w)

    T = {}
    L = [W()]
    for a in w:
        todo = [(W(),T)] 
        while todo:
            cw, t = todo.pop()
            todo.extend((cw+W(b),tt) for b,tt in t.items())
            if a not in t:
                t[a] = {}
                L.append(cw + W(a))

    return L