trac #17013: new class WordDatatype_char
trac #17013: added is_square in WordDatatype_char
Implement naive algorithm for factor_set method
trac #17013: doctests improvements + bug fix
Trac #17013: WordDatatype_char

Creation of a new class WordDatatype_char that has in backend an
'unsigned char *' and use it wherever possible. The implementation is
much faster than anything else but is only available for alphabet
contained in [0,255].

URL: http://trac.sagemath.org/17013
Reported by: vdelecroix
Ticket author(s): Vincent Delecroix
Reviewer(s): Sébastien Labbé
Trac #17016: Implement naive algorithm for factor_set method of a finite word

Because it allows to compare the suffix tree implementation with the
naive approach which simply uses a sliding window. With #17013, the
naive approach might be faster...

Though, the following example shows the suffix tree is faster::

{{{
    sage: w = Word([randint(0,2) for _ in range(100000)],
alphabet=[0,1,2])
    sage: %time L = [w.number_of_factors(i, algorithm='naive') for i in
range(20)]
    CPU times: user 6.9 s, sys: 294 ms, total: 7.2 s
    Wall time: 7.17 s
    sage: %time O = [w.number_of_factors(i, algorithm='suffix tree') for
i in range(20)]
    CPU times: user 6.34 s, sys: 131 ms, total: 6.47 s
    Wall time: 6.52 s
    sage: %time O = [w.number_of_factors(i, algorithm='suffix tree') for
i in range(20)]
    CPU times: user 3.64 s, sys: 28.3 ms, total: 3.67 s
    Wall time: 3.76 s
    sage: %time L = [w.number_of_factors(i, algorithm='naive') for i in
range(20)]
    CPU times: user 6.64 s, sys: 302 ms, total: 6.94 s
    Wall time: 6.93 s
}}}

URL: http://trac.sagemath.org/17016
Reported by: slabbe
Ticket author(s): Sébastien Labbé
Reviewer(s): Vincent Delecroix