We are not always satisfied with finding locations where a pattern matches exactly. Sometimes we could, for example, want to find all occurrences of a word and include occurrences where the word is misspelt. Searching for “almost matches” is called approximate search. We will look at a suffix tree–based approach and a BWT-based approach. Considering the experimental results from the last chapter, it might seem odd to consider a BWT approach instead of a suffix array approach, but there is a reason for this: we can add a trick to the BWT approach to make it faster than the suffix tree solution ...
Get String Algorithms in C: Efficient Text Representation and Search now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
