FM-index - Count

The operation count takes a pattern P and returns the number of occurrences of that pattern in the original text T. Since the rows of matrix M is sorted, and it contains every suffix of T, the occurrences of pattern P will be next to each other in a single continuous range. The operation iterates backwards over the pattern. For every character in the pattern, the range that has the character as a suffix is found. For example, the count of the pattern "bra" in "abracadabra" follows these steps:

1. The first character we look for is a, the last character in the pattern. The initial range is set to + 1..C = . This range over L represents every character of T that has a suffix beginning with a.
2. The next character to look for is r. The new range is + Occ(r, start-1) + 1..C + Occ(r, end)] = =, if start is the index of the beginning of the range and end is the end. This range over L is all the characters of T that have suffixes beginning with ra.
3. The last character to look at is b. The new range is + Occ(b, start-1) + 1..C + Occ(b, end)] = = . This range over L is all the characters that have a suffix that begins with bra. Now that the whole pattern has been processed, the count is the same as the size of the range: 8 - 7 + 1 = 2.

If the range at becomes empty or the range boundaries cross each other before the whole pattern has been looked up, the pattern does not occur in T. Because Occ(c, k) can be performed in constant time, count can complete in O(p) time.