045 Subsir

[•Dastas]

Imi spuneti va rog daca pentru exemplul:

abcabcaa
acbacba

Matricea Nr arata in felul urmator:

Cod:

1 1 1 1 1 1 1
1 1 1 0 0 1 0
1 1 0 0 1 0 0
1 0 0 2 0 0 1
1 0 1 0 0 3 0
1 1 0 0 3 0 0
1 0 0 1 0 0 6
1 0 0 1 0 0 7

Multumesc.

[•DITzoneC]

La mine arata:

Cod:

1 0 0 1 0 0 1 
0 0 1 0 0 1 0 
0 1 0 0 1 0 0 
1 0 0 2 0 0 1 
0 0 1 0 0 3 0 
0 1 0 0 3 0 0 
1 0 0 1 0 0 6 
1 0 0 1 0 0 7 

dar eu am calulat doar pentru perechile (i,j) pentru care s1(i)==s2(j) deoarece doar de ele aveam nevoie. In rest am pus 0 deci este cam acelasi lucru cu a ta.

[•Dastas]

Multumesc! am luat pana la urma 100.

[•Andreid91]

Ahhhhhhhhh... de ce imi da WA doar pe al 9-lea test?
Doar am calculat mereu rezultatul partial in modulo 666013

[•Andreid91]

Aici am sursa comentata

[•DITzoneC]

Vad ca nu ai pus peste tot modulo. Cand calculezi nr[ i ][ j ] trebuie sa pui si acolo modulo pentru ca pot fi si ele foarte mari.

Si alta data nu mai posta de 2 ori consecutiv (foloseste edit / modifica)

[•Andreid91]

asta era.mersi

[•basketbalistu92]

pai nu iei fiecare litera si cauti si urm in sirul b?

[•popoiu.george]

Iau 70pct, si ma chinui de 4 ore la problema asta.   Pe tesul acesta imi da matricea Nr la fel ca celor care au mai postat inaintea mea.

Cod:

subsir.in
abcabcaa
acbacba

Iau WA pe testele 4,5 si 9. Problema cred ca este la calcularea solutiei. Matricea Nr cred ca o calculez bine. Am citit si pe forum si in aricolu cu solutii, dar nu prea am inteles cum sa determin solutia.

Imi puteti explica? Multumesc anticipat!

P.S: Eu determin solutia parcurgand matricea Nr, si iau cel mai mare Nr[ i ][j] pentru care cmls[ i ][j]=lungimea celui mai lung subsir comun si                a[ i ]==b[j] , si ma indoiesc ca e corect...


L.E. : Am rezolvat, era de la calcularea solutiei.