in reply to Re: Finding repeat sequences. (only mostly regex)
in thread Finding repeat sequences.

I assume that the pattern must repeat at least twice, otherwise, the full string is always the longest answer.

I wish that were the case. It mostly will be, but sometimes the string will consist of 1 complete and 1 partial rep.

But the partial rep at the end *will* exactly match the same number of characters at the beginning of the string, so it will always be possible to determine the rep.

But how to encode that in a regex or at least avoid a brute force chop and compare?

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.
  • Comment on Re^2: Finding repeat sequences. (only mostly regex)

Replies are listed 'Best First'.
Re^3: Finding repeat sequences. (only regex)
by tye (Sage) on Jun 18, 2013 at 20:13 UTC

    Note that, based on that definition, if the first and last characters are the same, then the answer is "the string minus the last character". Which leads to: 

    /^(.+?).*\1$/

    [download]

    Which leads to a full solution of: 

    /^((.*?).*?)\2*\1$/

    [download]

    which might be horribly inefficient (at least for some cases) or might not; I haven't considered it.

    - tye        

[reply]
[d/l]
[select]

      Nice reversal of the logic and closer:

      $s = 'aaaabaaaabaaaaabaaaab';;
$s =~ /^((.*?).*?)\2*\1$/ and print "$2/$1";;
a/aaaabaaaab

      [download]
      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.
[reply]
[d/l]

        I think I had \1 and \2 backward. Then you just have to disallow the trivial solution: 

        $s = 'aaaabaaaabaaaaabaaaab';
$s =~ /^((.*?).*?)(?=.)\1*\2$/ and print "$2/$1";

        [download]

        (Update: Dropped the unneeded () around \1 that I had introduced while debugging. You probably also need to change .*? to .* so you get the longest solution not the shortest.)

        - tye        

[reply]
[d/l]
Re^3: Finding repeat sequences. (only mostly regex)
by choroba (Cardinal) on Jun 18, 2013 at 20:10 UTC
    Cannot you find the incomplete repetition with 
    /^(.*).*\1$/

    [download]
    ?

    If it is complete, you get the whole one.

    لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ
[reply]
[d/l]

      There are no gaps between the repeats, so the uncaptured .* is not required (actually mustn't be there).

      And if the second rep is incomplete \1 will never match before $.

      I've been trying variations on 

      $s = 'aaaabaaaabaaaaabaaaab';;
$s =~ m[^(.+)\1*(.*?$)] and $1 =~ $2 and print "$1/$2";;
aaaabaaaabaaaaabaaaab/

      [download]

      With the idea that any partial rep at the end can be verified again the beginning of the full rep, but it needs to happen inside the regex and cause backtracking.

      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.
[reply]
[d/l]
        The .* matches the missing part of the last incomplete repetition.
        لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ
[reply]
[d/l]

In Section Seekers of Perl Wisdom