#!/usr/bin/perl -w

use strict;


my ($left, $right, @a, $ok, @rslashes);


sub work
{
  my $tests;
	$left = shift;
	$right = shift;
	@a = ();

	my $len = length($left);
	$ok = "";
	vec($ok, $len, 1) = 1;
	my $all = "";
	for (0..$len) {
		vec($all, $_, 1) = 1;
	}

	my %right;
	for my $i (0..$len - 1) {
		push @{$right{lc substr $right, $i, 1}}, $i;
	}
	for my $i (0..$len - 1) {
		for my $j (@{$right{lc substr $left, $i, 1}}) {
			my $v = "";
			vec($v, $j, 1) = 1;
			$v |= $ok;
			$a[1][$i]{$v} = { l => $j, r => $j + 1, n => 1 };
		}
	}
        1;

	for my $l (2..$len) {
		for my $i (0..$len - $l) {
			my %ok;
			my $best = 999999;
			for my $ll (1..$l - 1) {
				my $j = $i + $ll;
				my $lr = $l - $ll;
				for my $vl (keys %{$a[$ll][$i]}) {
					next if $a[$ll][$i]{$vl}{n} > $best;
					for my $vr (keys %{$a[$lr][$j]}) {
                                                $tests++;
						next unless ($vl & $vr) eq $ok;
						my $al = $a[$ll][$i]{$vl};
 						my $ar = $a[$lr][$j]{$vr};
						my $n = $al->{n} + $ar->{n};
						$n-- if $al->{r} == $ar->{l};
						next if $n > $best;
						if ($n < $best) {
							$best = $n;
							%ok = ();
						}
						next if exists $ok{$vl | $vr};
						$ok{$vl | $vr} = { n => $n, l => $al->{l}, r => $ar->{r}, k => $vl };
					}
				}
			}
			$a[$l][$i] = {%ok};
		}
	}

	@rslashes = map "", (1..$len);

	sub rec
	{
		my ($l, $i, $v) = @_;

		return substr $left, $i, 1 if $l == 1;
		my $vl = $a[$l][$i]{$v}{k};
		my $vr = ($v ^ $vl) | $ok;
		my $ll = (unpack "%b*", $vl) - 1;
		my $lr = $l - $ll;
		my $j = $i + $ll;
		my $sl = rec($ll, $i, $vl);
		my $sr = rec($lr, $j, $vr);
		if ($a[$ll][$i]{$vl}{r} == $a[$lr][$j]{$vr}{l}) {
			return "$sl$sr";
		} else {
			$rslashes[$a[$ll][$i]{$vl}{r}] = "/";
			return "$sl/$sr";
		}
	}

	my $nparts = $a[$len][0]{$all}{n};
        return $nparts;
	my $nleft = rec($len, 0, $all);
	$rslashes[$a[$len][0]{$all}{r}] = "/";
	my $nright = join "", map { $rslashes[$_] . substr $right, $_, 1 } (0..$len - 1);

	# print "$nparts $nleft $nright\n";
        return $tests;
}

*min_chunks = \&work;

#my $prev = 1;
#for (2..15) {
#  my $z = "a" x $_;
#  my $n = work($z, $z);
#  printf "%2d: tests %6d (%2.2f)\n", $_, $n, $n/$prev;
#  $prev=$n;
#}

