Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number

Re^3: Finding repeat sequences.

by sundialsvc4 (Abbot)
on Jun 19, 2013 at 13:05 UTC ( #1039775=note: print w/replies, xml ) Need Help??

in reply to Re^2: Finding repeat sequences.
in thread Finding repeat sequences.

I think that the pseudo-coded solution is the strongest one, if it is made to stop after finding the longest possible substring (then last), and if it is allowed to find all possible (reasonably-long) tails, once again starting with the longest one.   (These would be what a human being would probably consider to be the best “right answers.”)

With very-short tails, as written it might produce wrong answers if it considers only the first two occurrences (consider string 'aaba' if the tail were merely 'a' .. incorrect).   But the essential idea, I think, is still valid.

One reason why I wrote it this way was in an effort to avoid “churning” memory when dealing with exceptionally-long strings.   You don’t need to consider any string that isn’t a tail, nor, within the head, any repeated-string candidate that won’t fit.   That subdivides the problem into two searches, both of which have only a few possibilities each.   It might not yet be bug-free, but it ought to be close . . .

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1039775]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (3)
As of 2018-04-21 08:19 GMT
Find Nodes?
    Voting Booth?