Algorithm to find the smallest snippet from searching a document?

Posted by deliciousirony on Stack Overflow See other posts from Stack Overflow or by deliciousirony
Published on 2010-06-02T02:27:59Z Indexed on 2010/06/02 2:33 UTC
Read the original article Hit count: 250

Filed under:

I've been going through Skiena's excellent "The Algorithm Design Manual" and got hung up on one of the exercises.

The question is: "Given a search string of three words, find the smallest snippet of the document that contains all three of the search words—i.e. , the snippet with smallest number of words in it. You are given the index positions where these words in occur search strings, such as word1: (1, 4, 5), word2: (4, 9, 10), and word3: (5, 6, 15). Each of the lists are in sorted order, as above."

Anything I come up with is O(n^2)... This question is in the "Sorting and Searching" chapter, so I assume there is a simple and clever way to do it. I'm trying something with graphs right now, but that seems like overkill.

Ideas? Thanks

© Stack Overflow or respective owner

Related posts about algorithm