Note de curs, clasele 9-10, 29 martie 2013

Teme din urmă

• Cel mai mare dreptunghi gol: se dă un dreptunghi și n puncte în el. Să se găsească cel mai mare dreptunghi care nu conține niciun punct.
  • Cătălin a bâlbâit rezolvarea, rămâne pentru data viitoare.

Căutări pe stringuri

Generalități

• Σ (alfabetul datelor de intrare)
• pattern (subșirul căutat): P de lungime m
• șirul în care căutăm: S de lungime n
• lungimea unui șir x se notează cu |x|
• shift (deplasare): un shift k suprapune patternul P[0...m-1] cu bucata din șir S[k...k+m-1]
• shift valid: cele două șiruri suprapuse sunt egale
• prefix (notație: a ⊏ b)
• sufix (notație: a ⊐ b)
• problema căutării: găsirea tuturor shifturilor valide

Proprietăți interesante:

• tranzitivitatea: dacă b ⊐ a și c ⊐ b, atunci c ⊐ a
• dacă a ⊐ b, atunci ax ⊐ bx pentru orice caracter sau șir x
• dacă x ⊐ z și y ⊐ z, atunci:
  • x ⊐ y dacă |x| < |y|
  • y ⊐ x dacă |y| < |x|
  • x = y dacă |x| = |y|

Algoritmul naiv

• Încercăm pe rând toate shifturile. Există n - m + 1 shifturi, iar verificarea unuia durează O(m)
• complexitate O(m(n - m + 1)
• problema algoritmului naiv este că ignoră niște informații utile despre pattern
  • exemplu: dacă patternul este abcdef, iar literele abcd s-au potrivit în shiftul curent (dar litera e nu), atunci aș putea sări următoarele trei shifturi, căci sunt garantat invalide
• algoritmul naiv merge bine când toate literele din pattern sunt diferite -- O(n)
• merge bine și dacă șirul de intrare este aleator; dacă d este mărimea alfabetului, atunci complexitatea este

$O\left((n-m+1)\cdot (1+{\frac {1}{d}}+{\frac {1}{d^{2}}}+...+{\frac {1}{d^{m-1}}})\right)=O\left((n-m+1)\cdot {\frac {1-d^{m}}{1-d}}\right)<O(2n)$

Rabin-Karp

• exemplu pentru alfabetul Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
• interpretăm patternul ca pe un număr de m cifre în baza 10
• pe cazul general, nu putem stoca d^m pe un tip de date întreg, deci lucrăm modulo k
• alegem k astfel încât kd să încapă pe un tip de date întreg
• când semnătura patternului și semnătura shiftului curent sunt egale, recurgem la comparația caracter cu caracter
• tot O(mn) în cazul cel mai rău, dar O(m + n + mn/k) în practică

Cu automate finite

Am predat această secțiune pe fugă, mai mult prin exemple.

• ce face următorul automat? (am desenat un automat cu două stări care acceptă șirurile de 0 și 1 terminate într-un număr par de 0)
• ce face următorul automat? (am desenat un automat cu trei stări care acceptă șiruri de cifre divizibile cu 3)
• să se deseneze un automat care acceptă șiruri terminate în 01
• să se deseneze un automat care acceptă șiruri care conțin subșirul 001
• să se deseneze un automat care acceptă șiruri care conțin subșirul abacaba
• definiție formală pentru automate: un tuplu format din
  • Σ (alfabetul)
  • Q (mulțimea de stări)
  • q_0 (starea inițială)
  • F (mulțimea de stări finale)
  • δ : Q x Σ → Q (funcția de tranziție)
• dacă construim δ, restul algoritmului merge în O(1) per caracter, deci O(m) în total
• esența funcției δ: cel mai lung prefix care să fie și sufix
• deci δ(q, a) = max { k | P[0...k-1] ⊐ P[0...q-1]a }
• construcția naivă a funcției δ se face în O(m³ |Σ|)
• KMP ne ajută să o construim în O(m), deci independent de mărimea alfabetului

Nu am avut timp să vorbim despre KMP.