Re: [FWP] longest substring with unique characters

[Jeff Pinyan <jeffp@crusoe.net>]

On Jan 19, Jeff Pinyan said:

>I hope this can be optimized more, though.

Uh, duh.  I create an array.  Uselessly.

>#!/usr/bin/perl -w
>
>use strict;
>
>while (<>) {
>  chomp;
>  my @longest = pinyan_UCS($_);
>  my $str = $_;
>
>  print map substr($str, $_->[0], $_->[1] - $_->[0]) . "\n", @longest;
>  print "\n";
>}
>
>
>sub pinyan_UCS {
>  my $str = shift;
>  my $len = length $str;

Kill this line: my @c = split //, $str;

>  my ($diff,$biggest) = (0,0);
>  my (@ahead,@matches);
>
>  for (my $i = 0; $i < $len; ) {

Kill this line: my $c = $c[$i];

>    my $match = [ $i, $len, $i+1 ];
>
>    if ($len - $i >= $biggest) {
>      for (my $k = $i; $k < $match->[1]; $k++) {

Change this line: $ahead[$k] ||=  index($str, $c[$k], $k+1);
To:               $ahead[$k] ||=  index($str, substr($str,$k,1), $k+1);

>        if ($ahead[$k] != -1 and $match->[1] > $ahead[$k]) {
>          $match->[1] = $ahead[$k];
>          $match->[2] = $k+1;
>        }
>      }
>
>      $diff = $match->[1] - $match->[0];
>
>      if ($diff > $biggest) { ($biggest,@matches) = ($diff,$match) }
>      elsif ($diff == $biggest) { push @matches, $match; }
>    }
>    else { last }
>
>    $i = $match->[2];
>  }
>
>  return @matches;
>}

-- 
Jeff "japhy" Pinyan     japhy@pobox.com    http://www.pobox.com/~japhy/
CPAN - #1 Perl Resource  (my id:  PINYAN)       http://search.cpan.org/
PerlMonks - An Online Perl Community          http://www.perlmonks.com/
The Perl Archive - Articles, Forums, etc.   http://www.perlarchive.com/


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