h2. 'Swap':problema/swap

Vom construi un o permutare $P$ a multimii ${1,...,N}$, asociata primului sir ($N$ este lungimea fiecaruia din cele $2$ siruri). Pentru fiecare caracter $x$ din primul sir, vom calcula al catelea caracter de tipul respectiv este in cadrul primului sir (acest lucru se poate realiza usor in $O(N)$). Apoi vom construi permutarea $P$ in felul urmator: pentru fiecare caracter $x$, pentru care stim ca este al $y$-lea caracter de tipul sau si care se afla pe pozitia $i$, vom seta valoarea lui $P[i]$ ca fiind egala cu pozitia pe care se afla cel de-al $y$-lea caracter egal cu $x$ din cel de-al doilea sir. Numarul de operatii $swap$ necesare este egal cu numarul de inversiuni ale permutarii $P$. Acest numar poate fi determinat eficient in mai multe feluri: mergesort modificat, arbori de intervale, arbori indexati binar etc.
 

h2. 'Obj':problema/obj
h2. '1expr':problema/1expr