[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
More information about the linux
mailing list