wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

minimal_absent_word (440B)

      1 # Minimal absent word (MAW)
      2 
      3 minimal word which is not a [factor] of a [word] but every shorter word is
      4 
      5 given a word, there is a linear number of minimal absent words
      6 
      7 - [directed_acyclic_word_graph] (DAWG)
      8   representing all [factors] of the word
      9   - [fujishige2023linear]
     10   - compact DAWG (CDAWG), keep only branching nodes + path compression
     11 
     12 variant [minimal_rare_word] with a threshold on the number of occurrences
     13 
     14 Up: [stringology]