sub state {
1&index" AKALCAARAZCOCTDCDEFLGAHIIAIDILINKSKTKYLAMAMDMEMIMNNCMOMSMTOHN
+DNENHNJNMPANVNYOKORRISCSDTNTXUTVAVTWAWIWVWY",pop
}
[download]

The character string was constructed to ensure that a valid state would never match a non-valid boundary. It was easier than I thought:

#!/usr/bin/perl
use strict;
$|++;

my @states = qw(
AK AL AR AZ CA CO CT DC DE FL GA HI IA ID IL IN KS
KT KY LA MA MD ME MI MN MO MS MT NC ND NE NH NJ NM
NV NY OH OK OR PA RI SC SD TN TX UT VA VT WA WI WV
WY
);

my %states = map { $_ => 1 } @states;

try("", \@states);

sub try {
  print "try: $_[0] @{$_[1]}\n";
  my $prefix = shift;
  my @later = @{+shift};
  unless (@later) {
    print "WINNER: $prefix\n";
    exit;
  }
  for my $i (0..$#later) {
    my $prefix2 = "$prefix$later[$i]";
    if (length $prefix2 < 3 or not $states{substr($prefix2, -3, 2)}) {
      ## worth recursing
      try($prefix2, [@later[0..$i-1, $i+1..$#later]]);
    }
  }
}
[download]

-- Randal L. Schwartz, Perl hacker