#!/usr/bin/perl

=begin

How many block moves does it take to transform one string to another?

algorithm taken from:
the string-to-string correction probem by Walter F. Tichy
ACM Transactions on Computer Systems Vol 2 No 4 Number 1984 p. 309-321

=cut

use strict;
use warnings;
use v5.10;

my @s = split //, shift || "shanghai rulez";
my @t = split //, shift || "sakhalin rulez";

# lengths

my $n = $#t;
my $m = $#s;

my ( $p, $q, $l ) = ( 0, 0, 0 );

while ( $q <= $n ) {
    ( $p, $l ) = f($q);

    printf( "p=%d\tq=%d\tl=%d\n", $p, $q, $l ) if ( $l > 0 );
    $q = $q + ( 1, $l )[ 1 < $l ];    # max(1,l) ... Perlmonks
}

sub f {
    my ($q)  = @_;
    my $pCur = 0;
    my $l    = 0;
    my $p    = 0;
    while ( ( $pCur + $l <= $m )
        and ( $q + $l <= $n ) )
    {

        my $lCur = 0;
        while ( ( $pCur + $lCur <= $m )
            and ( $q + $lCur <= $n )
            and ( $s[ $pCur + $lCur ] eq $t[ $q + $lCur ] ) )
        {
            $lCur++;
        }
        if ( $lCur > $l ) {
            $l = $lCur;
            $p = $pCur;
        }
        $pCur++;
    }
    return ( $p, $l );
}