Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?

Re^3: Finding repeat sequences.

by LanX (Bishop)
on Jun 21, 2013 at 02:22 UTC ( #1040055=note: print w/replies, xml ) Need Help??

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

here a regex solution which works for the shortest possible tail of length k

DB<127> $str => "abcdabcdabceabcdabcdabceab" DB<128> $str=~/^((.+?).*)\2$/; $rest=$1, $tail=$2 => ("abcdabcdabceabcdabcdabce", "ab") DB<129> $rest =~ /^(.+?)\1*$/; $1 => "abcdabcdabce"

needs to be extended for longer possible tails.

But taking the dimensions of your data I doubt that regexes are appropriate.

You could test all $patterns which repeat at least once (or x times) and calculate $k = $m % $l with $m =length ($str), and check if $str starts and ends with the same substring $tail of length $k and then check if the pattern continues repeating.

Or start eliminating all possible $tails and check if $l of a repeating pattern is a divisor of the $rest.

Had no time to check all the other posted solutions and don't wanna reinvent the wheel, so I better stop here! =)


Cheers Rolf

( addicted to the Perl Programming Language)

Replies are listed 'Best First'.
Re^4: Finding repeat sequences.
by BrowserUk (Pope) on Jun 21, 2013 at 02:48 UTC

    That looks suspiciously like a close variation on choroba's attempt.

    Had no time to check all the other posted solutions and don't wanna reinvent the wheel,

    All the tested solutions, along with how they faired in my test harness, are nicely grouped together in Re: Finding repeat sequences. (Results:Part 1).

    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.

Log In?

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

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (2)
As of 2017-11-19 18:00 GMT
Find Nodes?
    Voting Booth?
    In order to be able to say "I know Perl", you must have:

    Results (282 votes). Check out past polls.