Comment by lazamar

Why not search the FM-indexes directly? It is faster than the n-gram search and you can use the exact full text of the needle.