Using iteration for populating the hash is fairly simple, but recursion is tidy for dumping the structure:

#!/usr/bin/perl
use strict;
use warnings;

my %hash;

while (<DATA>) {
    my $parent = \%hash;

    chomp;
    for my $str (split ',') {
        $parent = $parent->{$str} ||= {};
        $parent->{count}++
    }
}

dumpHash (\%hash, '');


sub dumpHash {
    my ($hash, $indent) = @_;
    
    for my $child (sort keys %$hash) {
        next if $child eq 'count';
        print "$indent$child $hash->{$child}{count}\n";
        dumpHash ($hash->{$child}, "$indent   ");
    }
}

__DATA__
string1,string2,string3,string4
string3,string4
string1,string2,string3
string1,string3,string5
[download]

Prints:

string1 3
   string2 2
      string3 2
         string4 1
   string3 1
      string5 1
string3 1
   string4 1
[download]

Note that you need to keep a count and a hash (ref) of any child nodes for each parent node. Incrementing a hashref will not lead to a happy life!