## if there are no common words between the sentences, exit early next unless first{ exists $ua->{ $_ } } keys %{ $ub }; ## fragment both sentences, discarding one-word fragments ## and sorting them by number of words, longest first. @aFragments = sort{ @$b <=> @$a } grep{ @$_ > 1 } @{ fragmentSentence( $sa, $ub ) }; @bFragments = sort{ @$b <=> @$a } grep{ @$_ > 1 } @{ fragmentSentence( $sb, $ua ) }; ## Exit early if either sentence has no remaining fragments next unless @aFragments and @bFragments; my @best; ## For each A fragment for my $aFrag ( @aFragments ) { ## early exit if this fragment is shorter than the best so far next if @$aFrag <= @best; ## for each B fragment for my $bFrag ( @bFragments ) { ## Ditto early exit next if @$bFrag <= @best; ## Finally, perform the LCS algorithm my @lcws = lcws( $aFrag, $bFrag ); ## And save if its the longest yet seen @best = @lcws if @lcws > @best } } ## Skip if we didn't find one next unless @best; ## Output the sentence numbers and the best LCWS we found. printf "( %4d / %4d )=>[ %s ]\n", $ai, $bi, join( ' ', @best );