# [clug] Substring repetition detection

Michael Still mikal at stillhq.com
Wed Jun 25 20:53:08 EST 2003

On Wed, 25 Jun 2003, Martin Pool wrote:

> On 25 Jun 2003, Michael Still <mikal at stillhq.com> wrote:
>
> > Anyways, I can't think of a good answer. Any hints?
> Brute force and ignorance. :-)

This is a proof of concept in perl which seems to work. Thanks for
everyone's help. To use this, just pass in a bunch of arguements:

./repeat a b c a b c e f g d d d

-----------------
#!/usr/bin/perl

use strict;
my(\$inset, \$testinset, \$teststring, \$length, \$matchcount, \$count);

for(\$length = int(scalar(@ARGV) / 2); \$length != 0; \$length--){
for(\$inset = 0; \$inset < scalar(@ARGV) - \$length + 1; \$inset++){
\$teststring = buildstring(\$inset, \$length);
\$matchcount = 1;

if(\$teststring ne ""){
for(\$testinset = \$inset + \$length; \$testinset < scalar(@ARGV) - \$length + 1; \$testinset++){
if(\$teststring eq buildstring(\$testinset, \$length)){
\$matchcount++;
}
}

if(\$matchcount > 1){
\$ARGV[\$inset] = "";
for(\$count = 0; \$count < \$matchcount; \$count++){
\$ARGV[\$inset] = "\$ARGV[\$inset]\$teststring ";
}
for(\$count = 0; \$count < \$matchcount * \$length - 1; \$count++){
\$ARGV[\$inset + \$count + 1] = "";
}
}
\$inset += \$matchcount - 1;
}
}
}

for(\$count = 0; \$count < scalar(@ARGV) + 1; \$count++){
if(\$ARGV[\$count] ne ""){
print "\$ARGV[\$count]\n";
}
}

sub buildstring(){
my(\$inset, \$length) = @_;
my(\$str, \$count);

\$str = "";
for(\$count = 0; \$count < \$length; \$count++){
\$str = "\$str\$ARGV[\$count + \$inset]";
}

return \$str;
}
-----------------

Now to go an do the real thing in C with a bunch of linked lists...

Cheers,
Mikal

--

Michael Still (mikal at stillhq.com) | Stage 1: Steal underpants
http://www.stillhq.com            | Stage 2: ????
UTC + 10                          | Stage 3: Profit