The following works for me:

$b=this_code_is_from_perlmonks_org;

for my $a(some_program_was_written_for_perlmonks_org=~/[st]/g){
    print $a,sprintf '%4s','*'x(2+($a cmp $b)), qq(\n);
    $b=$a
}
[download]

Update: I didn't get the requirement of outputting different depths, so here is an improved variation on the same theme:

$level=12;
my $i=12;
my $l=$level-12;
$_ = #$;

this_program_source_was_written_for_the_site_perlmonks_org.
please_do_not_give_this_code_to_your_teacher_without_understanding.
We_value_learning_but_the_work_has_to_be_done_by_yourself.
kthxbai;

$b=a_program_written_by_Corion;

for $a(($_.reverse)=~/[sx]/g){
    $d=($a cmp $b)||$d;
    $l+=$d;
    $b=$a;
    print sprintf '%'.$i.'s', '*'x$l, qq(\n)
        unless $l<0
}
[download]