Opened 13 years ago
Last modified 13 years ago
#7642 needs_work enhancement
Add an implementation of LCA to sage.combinat.words.suffix_trees
Reported by: | Arnaud Bergeron | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | |
Component: | combinatorics | Keywords: | lca suffix_tree |
Cc: | Merged in: | ||
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
I have implemented the linear time preprocessing, constant-time queries algorithm for the lowest common ancestor (LCA) in the context of the suffix trees for words.
The only thing I'm not very sure about is where to place the bit manipulation functions.
Attachments (1)
Change History (5)
Changed 13 years ago by
Attachment: | trac_7642.patch added |
---|
comment:1 Changed 13 years ago by
Status: | new → needs_review |
---|
comment:2 Changed 13 years ago by
comment:3 Changed 13 years ago by
Owner: | Sage Combinat CC user deleted |
---|
Has this been checked on Solaris?
There's general information about building on Solaris at
Information specifically for 't2' at
http://wiki.sagemath.org/devel/Building-Sage-on-the-T5240-t2
Both the source (4.3.0.1 is the latest to build on Solaris) and a binary which will run on any SPARC can be found at http://www.sagemath.org/download-source.html
Dave
comment:4 Changed 13 years ago by
Status: | needs_review → needs_work |
---|
Several comments about this patch :
What you are doing in this patch is out of my field, so my remarks could just come from this. I thought it would just be an algorithm on trees, but many details not being explicit in the docstrings, it is difficult for me to fill the holes... :-)
Nathann