use warnings;
my @iparray=( "ab",  "bd","d");
my @sortedarray=sort(@iparray);
my @oparray;
my $lowerlimit=0;
my $upperlimit=0;
my $count=0;
my $inc=1;
my $mat=0;
my $matchedstring;
my @regexarray;
sub shrink
{
	my $low = 0;
	my $up = 1;
	my $len = scalar @sortedarray;
	my $inc = 1;
	for (;$inc< $len;$inc++)
	{
		if ($sortedarray[$low] eq $sortedarray[$up])
		{
			splice(@sortedarray, $up , 1);
		}
		else
		{
			$up++;
			$low++;
		}
	}
}
sub regexp
{
	my $inc = 0;
	my $regex;
	if(length($matchedstring ne ""))
	{
		$regex = $matchedstring . '[';
	}
	else
	{
		$regex = '[';
	}
	for (;$inc < scalar(@oparray); $inc++)
	{
		$regex = $regex . $oparray[$inc];
		if (($inc+1)<scalar(@oparray))
		{
			$regex = $regex.'|';
		}
	}
	$regex = $regex . ']';
	#print $regex;
	push @regexarray , $regex;
	@oparray = ();
	return;
}
sub splitter
{
        #If the match is zero then increase the lowerlimit by one and call the func subroutine to identify other matches
    
        #Else get the matched and unmatched substring from lowerlimit to upperlimit and store it into an array
    
                #Get the matched substring
        $matchedstring=substr($sortedarray[$count-1],0,$mat);
print("\n",$matchedstring);
        my $temp=$upperlimit; 
        print("\n1.",$temp);   
                #Traverse from lowerlimit to upperlimit to get the unmatched substring and store it into an array        
        while($temp>=$lowerlimit)
            {
                $word=substr($sortedarray[$temp],$mat,length($sortedarray[$temp]));
                if($word eq "")
                    {
                    push @oparray,"\\s";
                    }
                else
                    {
                    push @oparray ,$word;
                    }                               
                    $temp--;
                
            } 
            regexp();           
         #print ("\n2.",@oparray);
           #print("\n3.",$upperlimit);
                        #If the upperlimit reached the size of the array then endthe application
            if(($upperlimit)==(scalar(@sortedarray)-1))
                {
				print @regexarray;
                die "Terminated ";
                #print "All the words are parsed";
                #last;
                }
                        #Else set the lowerlimit as upperlimit+1
            else
                {
                $lowerlimit=$upperlimit+1;
               # print ("4.",$lowerlimit);
                $count=$lowerlimit;
                $inc=1;
                func();
                }
        
}
#print "All the words are parsed";
sub func
{
#Get the specified number of characters from the word if it is defined in the array
if (defined $sortedarray[$count])
        {
        $base=substr($sortedarray[$count],0,$inc);
        #print ("\n5.",$base);
        }
                #Else terminate the application
        else
        {
		print @regexarray;
        die;
        }
                #Get the specified number of characters from the word if it is defined in the array
        if (defined $sortedarray[$count+1])
        {
                $match=substr($sortedarray[$count+1],0,$inc) ;
                #print ("\n6.",$match);
        }
                #If the second word is not matched then find whether there is a match between the previous two words.
                
        else
        {
        if (defined $sortedarray[$count-1])
                        {
                        
                        
                $s=substr($sortedarray[$count-1],0,$inc);
                #print ("\n7.",$sortedarray[$count-1]);
                #print ("\n8.",$s);
                #print ("\n9.",$count);
                }
                
                else
                {
                if($lowerlimit==0)
                        {
                        $upperlimit=$lowerlimit;
                        $mat=$inc-1;
                        splitter();
                        }
                }
                if($s eq $base)
                {
                $upperlimit=$count;
                $count = $lowerlimit;
                $inc++;
                #print $inc;
                func();
                }
                else
                {
                $upperlimit=$lowerlimit;
                $mat=0;
                splitter();
                }
                        }
       # print("\n",$base," ",$match);
        $count++;
        #print("\n10.",$count);
                #Determine whether the the two substrings were matched or not
        if($base ne $match)
            {
                        #If the mismatch occurs at the lower limit itself means call the splitter to split the word based on the no of matches
                if(($count-1) == $lowerlimit)
                    {
                    #print ("\n11.",$mat);
if(($mat==0))
{
if(($inc==1))
{
$upperlimit=$lowerlimit;
splitter();
}
}
                    my $lcount=$count;
                    my $ucount=$count+1;
                        #print("\n12.",$lcount,$ucount);         #If the end of the array is reached , call the splitter to split the unmatched and matched characters.
                    if($ucount>=scalar(@sortedarray))
                        {
                        $upperlimit=$count;
                        $mat=$inc-1;
                       # print("\n13.",$mat);
                        splitter();
                        }
                                                #If the mismatch occurs at the lowerlimit ,then parse the array upto the upperlimit and find any other words having the mathch
                        else
                        {
                        my $ulimit=$upperlimit;
                        #print ("\n13.",$ulimit);
                        #print("\n14.",$lcount,"\n",$ucount,"\n",$ulimit);
                        while($ulimit >= $count)
                            {
                            my $new=substr($sortedarray[$lcount],0,$inc);
                            #print("\n15.",$new);
                            my $new1=substr($sortedarray[$ucount],0,$inc);
                            #print("\n16. ",$new1);
                                                        #If the any two words have a match, then call the splitter to split the words before the matched words.
                            if($new eq $new1)
                                                                {
                                                                $upperlimit=$lcount-1;
                                                                #print("\n17.",$upperlimit);
                                                                $mat=$inc-1;
                                                                #print("\n18.",$mat);
                                                                splitter();
                                                                }
                                                        #Traverse the array until the end of the array is reached
                            else
                                {
                                                                $ulimit--;
                                                                $lcount++;
                                                                $ucount++;
                                                                #print("\n19.",$lcount,"\n",$ucount,"\n",$ulimit);
                                }
                            }
                        $mat=$inc-1;
                        #print $mat;
                        splitter();
                        }
                    }
                                #Else increment the substring counter and do the same by calling func subroutine        
                else
                    {
                    $inc++;
                    #print $inc;
                    unless(($count) == $upperlimit)
                        {
                        $count=$lowerlimit;
                        func();
                        }                               
                    }
            }
                #If the substrings were matched change the upper limit and call func subroutine to find whether there is any other words available with the same match.         
        else
            {
            $mat=$inc-1;
            #print("\n20.",$mat);
            $upperlimit=$count;
            func();
            }
}
shrink();
func();