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.

Σ (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|

Î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)$

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ă

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.