My guess: Perl is looking for exact strings from both ends, your regexes include a trailing "b" but your string $futile doesn't

This simplified demo seems to support my theory

D:\tmp\pm>perl -Mre=debug -E"'aaaa' =~/a*a*b/"
Compiling REx "a*a*b"
synthetic stclass "ANYOF[ab]".
Final program:
   1: STAR (4)
   2:   EXACT <a> (0)
   4: STAR (7)
   5:   EXACT <a> (0)
   7: EXACT <b> (9)
   9: END (0)
floating "b" at 0..9223372036854775807 (checking floating) stclass ANY
+OF[ab] min
len 1
Matching REx "a*a*b" against "aaaa"
Intuit: trying to determine minimum start position...
  doing 'check' fbm scan, [0..4] gave -1
  Did not find floating substr "b"...
Match rejected by optimizer
Freeing REx: "a*a*b"
[download]

please note Did not find floating substr "b"... Match rejected by optimizer