Per
Cea mai rapida solutie se bazeaza pe hashing. Pentru aflarea rezultatului vom construi o dinamica A[i][j] = numarul de secvente de lungime i concatenate care se termina in j.
Formula de recurenta este usor de dedus :
- Daca la pasul i,j sirul care incepe pe i-j+1 este identic cu cel de pe i-2j+1 atunci A[i][j] = A[i][j-i]+ 1
- alfel A[i][j] = 1;
Pentru a afla in O(1) daca doua siruri sunt egale vom construi H[i][j] = (ch[i] - 'a') * prim[ 1 ] + (ch[i+1] - 'a') + prim[ 2 ] + .. + (ch[j] - 'a' * prim[j-i+1] ) unde prim[i] va fi al i-lea numar prim si ch[i] este caracterul de pe pozitia i.
Desi nu in toate cazurile un hash ar da o solutie corecta aici este putin probabil sa apara 2 valori identice pentru siruri diferite.
La fiecare pas cand intalinim un A[i][j] >= K adunam la rezultat.
Pentru a se incadra in memorie este necesar sa mentinem doar ultima linie a matricii pentru hash si dinamica.
Compexitatea finala este O(N^2) ca timp si O(N) ca memorie.
