Input: A single long string (<10MB) and a number k
Definition: A unique k-substring is a substring of length k, which occurs exactly once in the input document.
Output (Approach 1): Either print each unique k-substring OR
Output (Approach 2): Output a DFA which matches unique k-substrings in the given document in a streaming fashion (KNP-style search)
Given a large string, I'd like to preprocess it find a "fingerprint" of all fixed-length (say, length 20) unique substrings. These are typically phrases specific to the document.
Then, I want to use find approximate copies of the document inside other documents. I have this process working already, it's just too slow.
So far, I've been looking at suffix tries and KNP-style search. Aho-Corasick algorithm adapts KNP to recognize multiple strings, and Incremental String Match, further allows adding strings while running. If I add removing search strings while running I think I'll be at a solution, but this is quickly getting complicated for a problem with such simple structure.
Is there a simpler algorithm / data structure, or a known one?