Zip
Problema se poate imparti in doua parti. Prima data se construieste un graf complet cu n noduri, in care ponderea unei muchii semnifica numarul maxim de caractere care pot fi comune daca cuvintele corespunzatoare nodurilor respective se scriu unul dupa celalalt. Dupa construirea grafului ramane sa determinam drumul cel mai lung, care contine exact m noduri. Numarul cautat va fi (m * k - lungimea acestui drum). Prima parte se poate rezolva cu algoritmul trivial in O(n2*k2), sau folosind functia prefix din algoritmul Knuth-Morris-Pratt in O(n2*k). A doua parte se poate rezolva cu metoda backtracking in O(nm). Evident, aceasta metoda este mult prea lenta, chiar si cu optimizarile posibile. O metoda mai rapida este folosirea metodei programarii dinamice si are o complexitate de O(n2*m). Se calculeaza matricea d, cu semnificatia: d[i,j] este drumul de lungime maxima, care trece prin i noduri si se termina in nodul j. Evident, valoarea cautata va fi max(d[m,i], i = 1, 2 ... n).
