Note de curs, clasele 9-10, 29 martie 2013
From Algopedia
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
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 dm 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(m3 |Σ|)
- KMP ne ajută să o construim în O(m), deci independent de mărimea alfabetului
Nu am avut timp să vorbim despre KMP.