Note de curs, probleme algoritmică, 8 noiembrie 2013

În acest curs am discutat problema 1989 - Subpalindromes.

Cerință

Se dă un șir de caractere. Asupra acestui șir de caractere se efecturează modificări și interogări.

Modificările presupun schimbarea caracterului de pe o poziție dată cu o valoare dată.

Interogările presupun determinarea caracterului de șir palindromic (șir care se citește la fel de la stânga la dreapta și de la dreapta la stânga) a unei subsecvențe dată a șirului.

Funcții hash pentru șiruri de caractere

Numărul unic asociat unui șir

Putem atribui fiecărui caracter distinct un număr unic. În cazul general, numărul atribuit unui caracter este codul său ASCII. Dacă avem garanția că vom procesa numai litere mici ale alfabetului englez (cum este cazul în problema discutată) putem atribui caracterelor 'a', 'b', ..., 'y' și 'z' numerele 0, 1, ..., 24 respectiv 25.

Notăm cu B (de la bază) numărul de caractere distincte și avem grijă ca toate numerele atribuite caracterelor să fie în intervalul discret [0, 255].

Pornind de la un șir de caractere, substituim fiecare caracter cu numărul său și obținem un șir de numere. Dacă privim aceste numere ca un șir de cifre în baza B, vom obține un număr (unic) în baza B asociat șirului.

Exemplu

Pentru a vizualiza mai bine, să presupunem că B = 10 și avem un șir în care apar doar primele 10 litere mici ale alfabetului englez.

șir de caractere: cada
șir de numere: 2, 0, 3, 0
cifre în baza 10: 2030 <- numărul (unic) asociat șirului

Cheia hash asociată unui șir

Alegem câteva (de regulă 1, 2 sau 3) numere prime mari (ex.: 1 000 000 007), notate P1, P2, ... Apoi calculăm resturile împărțirii numărului asociat șirului dat la fiecare dintre numerele prime alese. Acest tuplu de resturi formează cheia hash asociată unui șir de caractere.

Cu cât numerele prime alese sunt mai multe cu atât:

• crește (liniar) timpul necesar efectuării calculelor;
• scade (exponențial) probabilitatea de a obține chei hash identice pentru șirului de caractere diferite (coliziuni).

Nu este obligatoriu ca numerele alese să fie prime, dar șansa de producere a coliziunilor crește semnificativ dacă numerele nu sunt prime cu B.

Calcul modular

Calcularea numărului asociat unui șir este costisitoare atât ca timp de execuție - O(N^2) cât și ca memorie - O(N) dar și ca implementare, necesitând calcule pe numere mari.

Dar, pentru calcularea restului împărțirii acestui număr la P1 este suficientă efectuarea tuturor calculelor modulo P1. Astfel, calcularea restului se efectuează în O(N) timp, O(1) memorie și necesită calcule cu tipul de date long long (dacă P1 este mai mare ca ~40 000).

Arbori de intervale

Arborii de intervale sunt o structură de date bazată pe arbori binari care:

• împart un interval discret de N valori în subintervale tot mai mici, până la subintervale cu un singur element;
• permit obținerea oricărei subsecvențe a intervalului inițial prin reuniunea a cel mult 2*log(N) subintervale disjuncte;
• orice element discret face parte din cel mult log(N) subintervale.

Exemplu de arbore de intervale:

[1  2  3  4  5  6  7  8]
      /          \      
[1  2  3  4][5  6  7  8]
   /    \      /    \   
[1  2][3  4][5  6][7  8]
 /  \  /  \  /  \  /  \ 
[1][2][3][4][5][6][7][8]

În nodurile arborelui de intervale se memorează informații asociate subintervalelor pe care le reprezintă. De exemplu, cheia hash a subsecvenței asociată nodului.

Datorită proprietăților arborilor de intervale următoarele operații sunt posibile în timp logaritmic:

• calcularea valorilor asociate oricărui subinterval;
• actualizarea valorilor stocate în arborele de intervale, în cazul modificării unui element discret.

Soluția problemei

Se menține un arbore de intervale discret de lungimea șirului de caractere dat. Pentru fiecare nod din arborele de intervale se reține cheia hash asociată subsecvenței de caractere corespunzătoare și cheia hash asociată aceleiași subsecvențe, dar cu caracterele așezate în ordine inversă.

Pentru fiecare interogare se calculează cheile hash ale subsecvenței interogată și ale subsecvenței interogată cu caracterele în ordine inversă. Dacă cele două chei sunt identice atunci, cu o probabilitate suficient de mare (două numere prime de ordinul 1 000 000 007 sunt suficiente), afirmăm că subsecvența are proprietatea de palindrom.