#14969: Longest common subword
---------------------------------+--------------------------------
Reporter: ncohen | Owner:
Type: enhancement | Status: positive_review
Priority: major | Milestone: sage-5.12
Component: combinatorics | Resolution:
Keywords: | Merged in:
Authors: Nathann Cohen | Reviewers: Hugh Thomas
Report Upstream: N/A | Work issues:
Branch: | Dependencies:
Stopgaps: |
---------------------------------+--------------------------------
Comment (by ncohen):
Hellooooooooo !!
> What I was thinking of was that l[i,j] would store a list of the longest
subwords of self[:i],other[:j]. Then at each step, you merge the three
lists l[i,j-1], l[i-1,j], and l[i-1,j-1] with self[i] tacked onto the end
of each one if self[i]==other[j], and remove the items that aren't as long
as the maximum.
>
> This wouldn't have the same complexity as the algorithm you implemented,
but that seems somehow not unreasonable, since you're asking for more
output. Is this inefficient?
Well it's fine. It's just that it would be slightly better to do the
computations twice : at first you only compute (and remember) all values
of l[i,j] (i.e. just the size of the longest subword), then in a second
pass you can actually build the list of longest subwords, from l[i,j] and
recursively to the smaller values of l, only when needed, i.e. when it
participates to a word of maximum length.
This way you make sure that you are not building and maintaining very long
lists of words which you would throw away later `:-)`
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/14969#comment:6>
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/groups/opt_out.
