#14969: Longest common subword
---------------------------------+-----------------------------
Reporter: ncohen | Owner:
Type: enhancement | Status: needs_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 hthomas):
Replying to [comment:3 ncohen]:
>
> Hmmmm. Well, the same algorithm with the same complexity can return the
number of longest common subwords too. In order to return all longest
subwords, though, one would have to keep track of all `l[i,j]`, and not
just `l[i,j]` and `l[i-1,j]`.
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?
--
Ticket URL: <http://trac.sagemath.org/ticket/14969#comment:4>
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.
