Fast word datatype using an array of unsigned char#

class sage.combinat.words.word_char.WordDatatype_char#

Bases: WordDatatype

A Fast class for words represented by an array unsigned char *.

Currently, only handles letters in [0,255].

concatenate(other)#

Concatenation of self and other.

EXAMPLES:

sage: W = Words([0,1,2])
sage: W([0,2,1]).concatenate([0,0,0])
word: 021000

has_prefix(other)#

Test whether other is a prefix of self.

INPUT:

other – a word or a sequence (e.g. tuple, list)

EXAMPLES:

sage: W = Words([0,1,2])
sage: w = W([0,1,1,0,1,2,0])
sage: w.has_prefix([0,1,1])
True
sage: w.has_prefix([0,1,2])
False
sage: w.has_prefix(w)
True
sage: w.has_prefix(w[:-1])
True
sage: w.has_prefix(w[1:])
False

is_empty()#

Return whether the word is empty.

EXAMPLES:

sage: W = Words([0,1,2])
sage: W([0,1,2,2]).is_empty()
False
sage: W([]).is_empty()
True

is_square()#

Return True if self is a square, and False otherwise.

EXAMPLES:

sage: w = Word([n % 4 for n in range(48)], alphabet=[0,1,2,3])
sage: w.is_square()
True

sage: w = Word([n % 4 for n in range(49)], alphabet=[0,1,2,3])
sage: w.is_square()
False
sage: (w*w).is_square()
True

length()#

Return the length of the word as a Sage integer.

EXAMPLES:

sage: W = Words([0,1,2,3,4])
sage: w = W([0,1,2,0,3,2,1])
sage: w.length()
7
sage: type(w.length())
<class 'sage.rings.integer.Integer'>
sage: type(len(w))
<class 'int'>

letters()#

Return the list of letters that appear in this word, listed in the order of first appearance.

EXAMPLES:

sage: W = Words(5)
sage: W([1,3,1,2,2,3,1]).letters()
[1, 3, 2]

longest_common_prefix(other)#

Return the longest common prefix of this word and other.

EXAMPLES:

sage: W = Words([0,1,2])
sage: W([0,1,0,2]).longest_common_prefix([0,1])
word: 01
sage: u = W([0,1,0,0,1])
sage: v = W([0,1,0,2])
sage: u.longest_common_prefix(v)
word: 010
sage: v.longest_common_prefix(u)
word: 010

Using infinite words is also possible (and the return type is also a of the same type as self):

sage: W([0,1,0,0]).longest_common_prefix(words.FibonacciWord())
word: 0100
sage: type(_)
<class 'sage.combinat.words.word.FiniteWord_char'>

An example of an intensive usage:

sage: W = Words([0,1])
sage: w = words.FibonacciWord()
sage: w = W(list(w[:5000]))
sage: L = [[len(w[n:].longest_common_prefix(w[n+fibonacci(i):]))
....:      for i in range(5,15)] for n in range(1,1000)]
sage: for n,l in enumerate(L):
....:     if l.count(0) > 4:
....:         print("{} {}".format(n+1,l))
375 [0, 13, 0, 34, 0, 89, 0, 233, 0, 233]
376 [0, 12, 0, 33, 0, 88, 0, 232, 0, 232]
608 [8, 0, 21, 0, 55, 0, 144, 0, 377, 0]
609 [7, 0, 20, 0, 54, 0, 143, 0, 376, 0]
985 [0, 13, 0, 34, 0, 89, 0, 233, 0, 610]
986 [0, 12, 0, 33, 0, 88, 0, 232, 0, 609]

longest_common_suffix(other)#

Return the longest common suffix between this word and other.

EXAMPLES:

sage: W = Words([0,1,2])
sage: W([0,1,0,2]).longest_common_suffix([2,0,2])
word: 02
sage: u = W([0,1,0,0,1])
sage: v = W([1,2,0,0,1])
sage: u.longest_common_suffix(v)
word: 001
sage: v.longest_common_suffix(u)
word: 001

sage.combinat.words.word_char.reversed_word_iterator(w)#

This function exists only because it is not possible to use yield in the special method __reversed__.

EXAMPLES:

sage: W = Words([0,1,2])
sage: w = W([0,1,0,0,1,2])
sage: list(reversed(w)) # indirect doctest
[2, 1, 0, 0, 1, 0]