<p><strong>Input</strong>: A single long string (&lt;10MB) and a number <em>k</em></p>

<p><strong>Definition</strong>: A <em>unique k-substring</em> is a substring of length k, which occurs exactly once in the input document.</p>

<p><strong>Output (Approach 1)</strong>: Either print each unique k-substring OR</p>

<p><strong>Output (Approach 2)</strong>: Output a DFA which matches unique k-substrings in the given document in a streaming fashion (<a href="https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm" rel="nofollow noreferrer">KNP</a>-style search)</p>

<p>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. </p>

<p>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.</p>

<p>So far, I've been looking at suffix tries and KNP-style search. <a href="https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm" rel="nofollow noreferrer">Aho-Corasick algorithm</a> adapts KNP to recognize multiple strings, and <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.154.9962&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">Incremental String Match</a>, 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.</p>

<p>Is there a simpler algorithm / data structure, or a known one?</p>

CC BY-SA 4.0
2020-06-04T17:41:45.093Z
Did you try Rabin-Karp? Suffix trees will also work (as they usually do) but are more complicated.
David Eppstein
CC BY-SA 4.0
2020-06-05T04:51:08.417Z
Can you recommend a <50page text about suffix trees and applications?

I haven't tried Rabin-Karp or any hashing (well, my python prototype...). A hash also reduces memory from a trie, which is turning out to be my limiting factor. I'd love to compare everything vs everything, but with millions of documents, a trie can't fit in main memory. I have to compare one subset vs everything, then the next subset vs everything, etc. Halving memory usage halves the number of passes. It looks like I may not have picked the right subproblem, open to suggestions.
Zachary Vance
CC BY-SA 4.0
2020-11-12T23:18:06.010Z
What I ended up finding useful to learn suffix trees was MIT's "Advanced Data Structures". Video lectures free at: https://www.youtube.com/playlist?list=PLUl4u3cNGP61hsJNdULdudlRL493b-XZf
Zachary Vance
<ds.data-structures><string-search>
Unique fixed-length substrings
Zachary Vance
# Unique fixed-length substrings

(Asked by: username_0 on 2020-06-04)

**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](https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm)-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](https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm) adapts KNP to recognize multiple strings, and [Incremental String Match](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.154.9962&rep=rep1&type=pdf), 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?

**Tags:** ds.data-structures, string-search

> **Comments:**
> **username_1**: Did you try Rabin-Karp? Suffix trees will also work (as they usually do) but are more complicated.  
> **username_0**: Can you recommend a <50page text about suffix trees and applications?  I haven't tried Rabin-Karp or any hashing (well, my python prototype...). A hash also reduces memory from a trie, which is turning out to be my limiting factor. I'd love to compare everything vs everything, but with millions of documents, a trie can't fit in main memory. I have to compare one subset vs everything, then the next subset vs everything, etc. Halving memory usage halves the number of passes. It looks like I may not have picked the right subproblem, open to suggestions.  
> **username_0**: What I ended up finding useful to learn suffix trees was MIT's "Advanced Data Structures". Video lectures free at: https://www.youtube.com/playlist?list=PLUl4u3cNGP61hsJNdULdudlRL493b-XZf  

---

## 0 answers

