#!/usr/bin/perl

use strict;
use Data::Dumper;

# find all substrings

sub fas {

  my $w = shift;

  return [$w] if length $w == 1;

  my $c = substr($w,0,1,'');

  my @s = fas($w);

  return ([map("$c$_",@{$s[0]}),$c],@s);

}

sub min_chunks {

  my ($w1,$w2) = @_;

  # find all the substrings

  my @sw1 = fas($w1);
  my @sw2 = fas($w2);

  # make a hash of substrings in first word

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

  # lengthify grepped out non-existent ones from in the second lol

  @$_ = map { length $_ } grep { $in1{$_} } @$_ for @sw2;

  my $nsw2 = @sw2;

  # from back to front, work out the minimum chunks

  # stick in some Dumps to see what's going on

  for my $i (reverse(0..$#sw2)) {

    my $togo = $nsw2 - $i;
    my $min = $togo;

    for my $j (@{$sw2[$i]}) {

      if ($j == $togo) {

	$min = 1;
	last;
      }

      my $js = 1 + $sw2[$i + $j];

      $min = $js if $js < $min;
    }

    $sw2[$i] = $min;
  }

  return $sw2[0];
}

print min_chunks('fbcbab','fbabcb')."\n";


