[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