#16935: Faster palindromes function for the Words library
-------------------------------------+-------------------------------------
Reporter: nadialafreniere | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.4
Component: combinatorics | Resolution:
Keywords: words, finite | Merged in:
words, palindromes | Reviewers:
Authors: Nadia Lafrenière | Work issues:
Report Upstream: N/A | Commit:
Branch: | 05cbe2844498c4c1f3d325e4ac27e637188b8e71
u/nadialafreniere/16935 | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by nadialafreniere):
I think I've given an answer t almost all the comments in the list above.
However, for number 11., I haven't found a better way to do it. The idea
is to avoid to count outside of the string. For example, I don't want to
test if w[-1]==w[n] for a word w, since I don't want the palindromes in
the circular word. Any suggestion would be very welcome!
For number 15., the reason I pretend the new algorithm is faster is that
the list of the lengths of longest palindromic suffixes is computed in
linear time for any type of words. With the actual version of the SAGE
library, for words having large palindromes, it can be much more than
that. For example, let r be is a prefix of w with lps(r) long enough.
Then, if the length of lps(ra) is smaller than |lps(r)|, where a is the
letter after r in w, it will call p.is_palindrome() on each suffix p
(starting with the greatest) of lps(r)a. Just to compute this entry of the
list, it could take a time up to (|lps(r)|)^2.
--
Ticket URL: <http://trac.sagemath.org/ticket/16935#comment:17>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
