. Since the rows of matrix are sorted, and it contains every suffix of , the occurrences of pattern 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: The first character we look for is , the last character in the pattern. The initial range is set to . This range over represents every character of that has a suffix beginning with a. The next character to look for is . The new range is , if is the index of the beginning of the range and is the end. This range over is all the characters of that have suffixes beginning with ra. The last character to look at is . The new range is . This range over 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: . If the range becomes empty or the range boundaries cross each other before the whole pattern has been looked up, the pattern does not occur in . Because can be performed in constant time, count can complete in linear time in the length of the pattern: time. Locate The operation locate takes as input an index of a character in and returns its position in . For instance . To locate every occurrence of a pattern, first the range of character is found whose suffix is the pattern in the same way the count operation found the range. Then the position of every character in the range can be located. To map an index in to one in , a subset of the indices in are associated with a position in . If has a position associated with it, is trivial. If it's not associated, the string is followed with until an associated index is found. By associating a suitable number of indices, an upper bound can be found. Locate can be implemented to find occ occurrences of a pattern in a text in time with bits per input symbol for any . Applications DNA read mapping FM index with backtracking has been successfully (>2000 citations) applied to approximate