# FM-index and pattern search with wildcards

in one of my algorithm courses i'm studying the FM-Index.

In one of the exercise I'm trying to do I was asked to give a procedure to search patterns of the form w* (where * indicates any character) using backwards search (see here).

How could this be possible? It seems to me that the algorithm already returns all the possible patterns of the form w* (because the starting range in which the search start is $0 - |T|$).And what kind of modification requires the procedure to search pattern in which for example one char is *, for example www*ww?

• Can anybody help me? – Fabrizio Duroni Nov 4 '14 at 21:19