#! /usr/bin/perl

=pod

Let us progress incrementally from simple parts but possibly incorrect, to a
program that fits the specs.

We want to remove the biggest common chunk at each iteration of the
two words $a and $b.  Let's write a program that does one iteration.
We create a string $s with "$a-$b" for value. A regular expression
will give use the biggest chunk common to $a and $b.


 my ($a,$b) = @ARGV;        # $a and $b are initalized by the two words
                            # given as parameters of the script
 $s = "$a-$b";       
 $s =~ m/(\w+).*?-.*?\1/;   # find the words common biggest chunk. or so we think.
 print "$1\n";              # prints the chunk

C<\w+> greedily matches an alphabetical chunk.  C<(\w+)> captures it.
There is no left anchor because the biggest chunk may not be at the
beginning of $s.  c<.*?-> match after the chunk until the next
string. To avoid unecessary backtracking we match non greedily.
C<\1> matches in the second word the chunk captured from the first.

 perl a1 abb bba # prints "a"

Bummer, this no different that if we had anchored our regexp.  Why?
The + and * quantifiers are greedy but the regexp engine first starts
a match starting at the first character and it finds one, even if that
does not necessarily mean that the capture is the biggest possible
one.

We have to start the search at the first character, the second and so
on. We can do that with C<$s =~ m/^.{$_}(\w+).*-.*?\1/> where $_ goes
from 0 to C<length $a>:

 map { $s =~ m/^.{$_}(\w+).*-.*?\1/  } 0.. $l;

Now we need to store the captures and keep the longest one.
C<$m[length$1]=$1> can be used. The longest capture will fall at the
end of the array. So we can retrieve it by popping the array.


 map { $s =~ m/^.{$_}(\w+).*-.*?\1/ and $m[length $1]=$1 } 0.. $l;
 my $m = pop @m;

So we have the longest chunk. Removing it from both words is quite easy.

     $s =~ s/$m(.*)$m/$1/;

We wrote the meat of each iteration.  Let us run our algorithm
manually with the word 'abbc' and 'bbac'.  At the beginning the
string is 'abbc-bbac' and at the first iteration it is 'ac-ac' and
after the second '-': we are done in two steps, meaning two chunks
have been removed.  But we should have three chunks, not two: 'bb',
'a' and 'c' are the three chunks. Removing 'bb' had the unwanted
effect to coalesce the two smaller chunks.  This is easy to fix,
instead of simply removing at each iteration the biggest common chunk
from each word, replace it by a non alphabetical character.

     $s =~ s/$m(.*)$m/#$1#/;

Now we can assemble our parts in a working program. We can afford the
luxury of pushing the removed chunks in the @m array that we will
eventually return.  In scalar context min_chunks() will have the
specified effect: returning the number of chunks.
   

=cut

use strict;
sub min_chunks { 
   my ($a,$b) = @_;
   my $s = "$a-$b";
   my $l = length $a;
   my @chunk;
   while(1) {
     my @m; # match strings sorted by increasing length
     map { $s =~ m/^.{$_}(\w+).*-.*?\1/ and $m[length $1]=$1 } 0.. $l;
     return @chunk unless @m;
     my $m = pop @m;
     push @chunk, $m;
     $s =~ s/$m(.*)$m/#$1#/;
   }
}

$,=',';
print  scalar min_chunks( 'addresser', 'readdress');
print  "\n";

=cut


  use strict;
  sub min_chunks { 
     my ($a,$b) = @_;
     my $s = "$a-$b";
     my @chunk;
     print "$s\n";
     while(1) {
       my ($m) = $s =~ m/(\w+).*-.*?\1/;
       return @chunk unless defined $m;
       push @chunk, $m;
       $s =~ s/$m(.*)$m/#$1#/;
       print "$s\n";
     }
  }

  $,=',';

  my  %ana = qw(
    aaab  aaba
    aaba  aaab  
   );

  for (keys %ana) {
    print  min_chunks($_, $ana{$_} );
    print  "\n\n";
  }



