No such thing as a small change PerlMonks

### Re^3: Finding repeat sequences.

by hdb (Monsignor)
 on Jun 19, 2013 at 07:46 UTC ( #1039739=note: print w/replies, xml ) Need Help??

in reply to Re^2: Finding repeat sequences.

UPDATE: WARNING: the following code does not work in all circumstances. Sorry!

Here is a variant of tobyink's solution that uses index to look ahead when the current candidate string repeats and then enlengthens (is that an English word?) it accordingly.

```sub find_substring
{
my \$input = shift;
my \$length = length \$input;
my \$i = 0;
my \$possible;
while( 1 ) {
\$possible = substr \$input, 0, \$i+1; # increase length by 1
\$i = index \$input, \$possible, \$i+1; # find next occurence of c
+andidate
return \$input if \$i < 0;            # if not found return full
+ string => no repetition
\$possible = substr \$input, 0, \$i;   # this is the minimum leng
+th candidate
return \$possible if \$input eq substr(\$possible x (1 + int(\$len
+gth / \$i)), 0, \$length); # success
}
}

UPDATE: Eily's solution below Re^3: Finding repeat sequences. can be used to avoid the construction of the repeated string (as it is the same just with offset). Therefore, this works even better:

```sub find_substring
{
my \$input = shift;
my \$length = length \$input;
my \$i = 0;
while( 1 ) {
\$i = index( \$input,  substr( \$input, 0, \$i+1 ), \$i+1);
return \$input if \$i < 0;
return substr( \$input, 0, \$i) if substr( \$input, \$i ) eq substr(\$i
+nput, 0, \$length - \$i);
}
}

Create A New User
Node Status?
node history
Node Type: note [id://1039739]
help
Chatterbox?
 [choroba]: backslashing them should help Discipulus ...Note that glob splits its arguments on whitespace.. [Discipulus]: oh it passed also some days ago iirc [Discipulus]: thanks

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (10)
As of 2018-03-20 12:03 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (250 votes). Check out past polls.

Notices?