Re: [FWP] longest substring with unique characters

[Daniel Chetlin <daniel@chetlin.com>]

On Thu, Jan 18, 2001 at 11:18:30PM -0500, Casey R. Tweten wrote:
> Dan Chetlin brought up this challenge on #perl and I accepted.

Damn you, Casey. I should have being doing real work!

This challenge came originally from a thread on clpmod, but it was
focused on RExen. Obviously other approaches are going to work better.

Here's what I finally came up with, in the "speed/algorithmic
satisfaction" category:

  #!/usr/bin/perl -w
  use strict;

  local $" = ',';
  while (<DATA>) {
    chomp;
    my @chars = split //;
    my $index = -1;
    my %seen = ();
    my $answer = [""];
    while (++$index < @chars) {
      if (exists $seen{$chars[$index]}) {
        answer_set(\%seen, $answer);
        $index = $seen{$chars[$index]};
        %seen = ();
      } else {
        $seen{$chars[$index]} = $index;
      }
    }
    answer_set(\%seen, $answer);
    print "$_: @$answer\n";
  }

  sub answer_set {
    my $seen = shift;
    goto 'JUMP_' . ((keys %$seen <=> length $_[0][0]) + 1);
    JUMP_0:
      return;
    JUMP_2:
      $_[0] = [];
    JUMP_1:
      push @{$_[0]},
        join "", sort { $seen->{$a} <=> $seen->{$b} } keys %$seen;
      return;
  }
  __DATA__
  mississippi
  abcbef
  adbcbef
  that
  abcdefa
  abcdabc
  testing
  this test
  abcdefg

Haven't done any benchmarking yet, but I'm betting on it so far (an ST
or GRT would probably speed it up a bit, though). This one gets all of
the longest unique strings.

Oh, and for the ObGolf category:

  perl -ple'my$m;do{local%s;/(((.)(?(?{$s{$3}++})(?!)))+)/g or$i=-1;
            $m=$1 if length$1>length$m}while pos=++$i;$_=$m'

(114 characters, including `perl' and the switches)

This one requires 5.6+ and only gets the first longest unique string.

Blah. Well, there goes a wasted worknight.

-dlc

==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe