Here is a regex-based solution. As Anonymous Monk has pointed out, the non-greedy quantifier ? is an important component. But to get all the matches, you need to loop:

#! perl
use strict;
use warnings;

my %matches;
my $s = 'zzAAABCDAAADCBAAABBDAAA';
my $t = $s =~ s/^[^A]*?(AAA.*)/$1/r;

while ($t =~ /^AAA.+?AAA/)
{
    my $u = $t;

    while ($u =~ /^(AAA.+?AAA)/)
    {
        my $match = $1;
        $match =~ s/\|/AAA/g;
        ++$matches{$match};
        $u =~ s/(AAA.+?)AAA/$1\|/;
    }

    $t =~ s/^AAA.+?(AAA.*)/$1/;
}

print $_, "\n" for sort keys %matches;
[download]

Output:

 0:15 >perl 563_SoPW.pl
AAABBDAAA
AAABCDAAA
AAABCDAAADCBAAA
AAABCDAAADCBAAABBDAAA
AAADCBAAA
AAADCBAAABBDAAA

 0:23 >
[download]

The inner loop finds successively longer matches by changing the AAA at the end of each match into a non-word character. The outer loop truncates the search string by removing everything up to the second AAA.

Hope that helps,