wiki_research

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

tape_construction (370B)

      1 # Tape construction
      2 
      3 [data_structure] for [infix_query] with [DFA] A on [word] w
      4 
      5 Gives [rectangular_complexity] O(|A| |w|) in time and space, and O(|Q|) query time
      6 
      7 [bojanczyk2009factorization] section 2.2
      8 
      9 The complexity is non-optimal, because O(1) instead of O(|Q|) can be achieved with a [data_structure] for [level_ancestor] queries
     10 
     11 Up: [tuple_testing_automaton]