How is it possible to print all patterns of length $k$ contained in a string, using the FM-index and Burrows-Wheeler transform?
PROBLEM DETAIL:
The input I have is:
- the text encoded with the Burrows-Wheeler Transform
- the data structure of the FM-Index.
In particularly for the second element listed, I have:
- $C(c)$ is a table that, for each character $c$ in the alphabet, contains the number of occurrences of lexically smaller characters in the text
- $Occ(c, k)$ is the number of occurrences of character $c$ in the prefix of the Burrows-Wheeler transform $1..k$
The only strategy that I've found at the moment is to reconstruct the text from the Burrows-Wheeler transform and, during that operation, for every char print the pattern that starts from it. In pseudocode,
---------------------------------------------
DATA
---------------------------------------------
bwt[n] => burrow wheeler transform of the text
C, Occ => FM-index data structure
K => lenght of the patterns to be extracted (so extract all patterns of length k from text T)
---------------------------------------------
Algorithm
---------------------------------------------
n = |bwt|; //text length
T[0,n]; //array used to save the original text
T[--n] = bwt[0]; //first char of the original text
currentIndex = 0;
for i = 0 to |btw(T)| - 1 do
//get original
lastFirst = c(bwt[currentIndex]) + Occ(bwt[currentIndex], currentIndex);
T[--n] = bwt[lastFirst];
currentIndex = lastFirst;
//print pattern only if we have reconstructed at least k char
if((|btw(T)| - n) >= k) from original text
print T[n, n+k]; //print last k char reconstructed
endif;
endfor;
Is there a better technique or strategy to solve the problem? Is there a strategy that doesn't need to reconstruct the original text?