#!/usr/bin/perl -w
use strict;

my $interesting = 5;  #minimum chunks considered interesting
my %seen;
while(my $list = <>){
#accept make_anagrams output as input
	chomp $list;
	next if $list =~ /\(See /;  
	my @words = split(/ /, $list);  #no error checking on input
	while( my $first_word = pop @words){
		foreach my $second_word (@words){
			my $first = lc($first_word);
			my $second = lc($second_word);
			my $id = join('+',sort($first, $second));
			next if $seen{$id};  #avoid "no, on; on, no" type problems
			$seen{$id} = 1;
			my $chunks = min_chunks($first, $second);
			if($chunks >= $interesting) {
				print "$first_word $second_word ($chunks)\n";
			}
		}
	}
}

sub min_chunks {
	my($word1, $word2) = @_;
	return 1 if $word1 eq $word2;
	return 0 if length($word1) != length($word2);
	return 0 if length($word1) == 1;
#generate a chunk pattern, starting with the lowest number of chunks (two, for efficency)
#compare chunk pattern for match.
#return on first successful match

	foreach my $size (2..length($word1)){ #chunk pattern size
		#determine chunk patterns for that size
		my @chunk_sizes = (1) x $size;
		$chunk_sizes[0] = length($word1)-$size+1;
#This breaks a word into a given number of chunks, of given
#So, for example, we may be at $size=4, with word
#length 6.  We try chunks sizes of 4,1,1,1; 3,2,1,1, and
# 2,2,1,1.  For each of those, we try each unique combination
# of orderings in terms of getting the chunks.  (4,1,1,1; 1,4,1,1;
# 1,1,4,1, 1,1,1,4

		while(defined $chunk_sizes[0]){
			#go through all combinations in that size
			my %seen;
			my %versionof1;
			my %versionof2;
		#factorial number of combos.  Ick.
		#go through in order
		#skip repeats.
			my @order = (0..$size-1);
			while (defined $order[0]){ 
				my $id = join('+', @chunk_sizes[@order]);
				unless($seen{$id}){
					
					#chunk both words, alphabetize, compare.
					my @chunks1;
					my @chunks2;
					my $point=0;
					foreach my $which_chunk_size (@order){
						push @chunks1, substr($word1,$point , $chunk_sizes[$which_chunk_size]);
						push @chunks2, substr($word2,$point , $chunk_sizes[$which_chunk_size]);
						$point += $chunk_sizes[$which_chunk_size];
					}
					my $baseform = join('', sort @chunks1);
					return $size if exists $versionof2{$baseform};
					$versionof1{$baseform} = 1;
					$baseform = join('', sort @chunks2);
					return $size if exists $versionof1{$baseform};
					$versionof2{$baseform} = 1;
				}
				$seen{$id}++;
				#don't waste time on order we've already seen.
				#(The next_order() function doesn't know what elements it's
				#telling you to rearrange, so it _will_ try to make you swap the
				#last two elements in 4,1,1,1
				@order = next_order(@order);
			}
			@chunk_sizes = next_chunks(@chunk_sizes);
		}
	}
}

sub next_chunks {
# This will change from 4,1,1,1 to 3,2,1,1 and so forth
	my @pattern = @_;
	my $point = $#pattern;
	while($point > 0){
		if($pattern[$point-1]-1 > $pattern[$point]){
			$pattern[$point-1]--;
			$pattern[$point]++;
			return @pattern;
		} else {
			$point--;
		}
	}
	return undef;
}



sub next_order {
# This cycles through the combinations of a sequence: 1,2,3,4
# then 1,2,4,3, then 1,3,2,4, and so forth.
	my @order = @_;
	my $point = $#order;
	while(($point > 0) and ($order[$point-1] > $order[$point])){
		$point--;
	}
	return (undef) unless $point;
	@order[$point, $point-1] = @order[$point-1, $point];
	splice(@order, $point, scalar(@order) - $point, sort @order[$point..$#order]);
	return @order;
}
