Counting substrings: in this text, find the number of substrings starting with A and ending with B

Question

For example, there are four such substrings in CABAAXBYA.

The original brute force algorithm I used was: using the external for loop, whenever I run into A, I go inside another loop to check if B is present or not. If B is found, I increase the score. Finally, the value stored in the count variable gives the desired result.

I came across a point while reading string matching algorithms, when you move from right to left, and not from left to right, your algorithm is more efficient, but here the substring is not indicated as a parameter of the function that you would use to calculate the required value.

My question is, if I cross the line from right to left, and not from left to right, will this make my algorithm more efficient anyway?

Answer 1

Here is one way in which repeating iteration over a line can result in O (n) being calculated instead of your original O (n ^ 2) job:

A = "CABAAXBYA" count = 0 # Number of B seen total = 0 for a in reversed(A): if a=='B': count += 1 elif a=='A': total += count print total 

This works by holding the track in the number of numbers B to the right of the current point.

(Of course, you can also get the same result iterating ahead by counting the number A instead:

 count = 0 # Number of A seen total = 0 for a in A: if a=='A': count += 1 elif a=='B': total += count print total 

)