[Date Prev][Date Next][Thread Prev][Thread Next] [Search] [Date Index] [Thread Index]

Re: [FWP] longest substring with unique characters




On 2001.01.19 05:18:30 +0100 Casey R. Tweten wrote:
> Dan Chetlin brought up this challenge on #perl and I accepted.

Another algorithm; this one founds all substrings with unique characters :

#!/usr/local/bin/perl -w
use strict;
my @lines = map { chomp; $_ } <DATA>;
foreach my $str (@lines) {
  my @substrings = ( substr $str, 0, 1 );
  for my $i ( 1 .. length($str) - 1 ) {
    my %seen = ();
    my $j = 0;
    for (reverse split //, substr $str, 0, $i + 1) {
      last if exists $seen{$_};
      $seen{$_} = 1;
      $substrings[$i] = ++$j;
    }
    $substrings[$i] = substr $str, $i - $j + 1, $j;
  }
  print "Longest substrings with unique characters for '$str':\n";
  my $maxlen = 0;
  for (map length, @substrings) {
    $maxlen = $_ if $_ > $maxlen;
  }
  print "'$_'\n" for grep { $maxlen == length } @substrings;
}
__DATA__
that
abcdefa
abcdabc
testing
this test

I'm sure it can be improved. At the moment, it looks like C.

-- 
Rafael Garcia-Suarez

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