Schema della sezione

  • Suffix array e Suffix tree

    • Definizioni. Array LCP. Passaggio da Suffix tree a suffix array e viceversa. Calcolo della sottostringa comune più lunga di 2 stringhe. (Gusfield 5, 5.1, 5.2, 5.3, 5.4, 7.4. dispensa)
    • Pattern matching su suffix array. Algoritmo e implementazione (Gusfield 7.14)
    • Ricerca della sottostringa comune più lunga di k stringhe: algoritmo e prima implementazione (Gusfield 7.4)
    • Range minimum query. Implementazione sottostringa comune più lunga di k stringhe.