Why is the run time exponential in the length of the string of a's? It seems like it should be at most O(n^3).

2^n is the number of subsets of the string of a's with no contiguity requirements. Nothing like this number of possible matches should need to be checked. What am I missing?