Patent ID: 8468162

Claim:
A method using circuitry for processing a substring with respect to a text string, comprising: storing in memory information for characters in a sorted BWT of a text string indicating a position of a first occurrence of each of those characters in the sorted Burrows-Wheeler transform (BWT) of the text string; storing in memory, for characters of an allowable alphabet, an ordered set of values indicating the number of occurrences of that character in preceding characters of a BWT of the text string, with the order of the values in the order of the characters of the BWT of the text string; initializing a signal indicating a first index to indicate a first position of the ordered set of values and initializing a signal indicating a second index to indicate a second position of the ordered set of values, the second position being different than the first position; iteratively receiving a signal indicative of a new character of a specified substring, setting, by the circuitry, the signal indicating the first index to indicate a first new position, the first new position being based on a sum of a) the value of the ordered set of values currently indicated by the position of the first index for the new character and b) the information indicating the first occurrence of the new character in the sorted BWT of the text string, and setting, by the circuitry, the signal indicating the second index to indicate a second new position, the second new position being based on a sum of c) the value of the ordered set of values currently indicated by the position of the second index for the new character and d) the information indicating the first occurrence of the new character in the sorted BWT of the text string; and providing, by the circuitry, a signal indicating that the specified substring does not appear in the text string if, for any characters of the specified substring, the position of the first index relative to the position of the second index within the ordered set of values is reversed compared to the initial position of the first index relative to the initial position of the second index within the ordered sets of value or if the position of the first index and the position of the second index within the ordered sets of values is the same position.