Another mention I'd make is that if some changes would be needed to the subs - like for example considering at least MIN_REPEATS repetitions of a string to be counted - I'm afraid it might be rather challenging in modifying the RX-ish solutions.
One simple solution is to go back to my (unposted) original solution and check MIN_REPEATS outside.
use constant MIN_REPEATS => 2; # Must have at least this many repeats
my $str = 'aabcdabcabcecdecd';
local our %counts;
$str =~ /(.{2,})(?{ ++$counts{$1} })(?!)/s;
delete @counts{ grep $counts{$_}<MIN_REPEATS, keys %counts };
use Data::Dumper;
print Dumper \%counts;
That way, there's nothing complicated left in the regex. The only part that's modifiable is /.{2,}/, which is easier to understand and modify than hand-rolled parsing code.
a regexp based solution would have to loose the fight against an approach that never has to look behind or ahead, but just touches every possible substring exactly 1 time
Not so! The above regex never has to look beind or ahead and touches every possible substring exactly 1 time.