Propozitie2
Pentru fiecare dintre cele C cuvinte se poate calcula un vector ap, care retine numarul de aparitii ale fiecarui caracter. Asadar ap[i][j] = numarul de aparitii ale caracterului j in cuvantul i.
Astfel pentru fiecare pozitie din sirul initial, se poate calcula in O(SIGMA) daca exista o permutare a unui cuvant care sa se potriveasca in sir, avand ultima pozitie cu care coincide, pozitia actuala. Relatia de recurenta este evidenta, Sol[i] = suma de Sol[i-L[j]], cuvantul j se potriveste in pozitia i, iar L[j] este lungimea cuvantului j. Asadar complexitatea finala este O(N*C*SIGMA), unde SIGMA in cazul de fata este 26
