•RazvanInfo10
Strain
Karma: 2
 Deconectat
Mesaje: 32
|
 |
« : Septembrie 23, 2013, 15:29:54 » |
|
Salut, am incercat sa rezolv o problema dar nu-mi iasa de nici o culoare, problema spune:
Fie n un număr natural și M={S1,S2,…,Sn} o mulțime de șiruri de caractere nevide. Fie Sk un șir de caractere din M. Atunci, orice caracter al lui Sk aparține mulțimii { 'a', 'b' }. Notăm prin |Sk| numărul caracterelor șirului Sk sau, echivalent, lungimea sa. O subsecvență Sk[i:j] a lui Sk este formată din caracterele situate pe pozițiile consecutive i, i+1, .., j. Astfel, dacă Sk = 'abbbaababa', atunci Sk[3:6] = 'bbaa' sau subsecvența evidențiată: 'abbbaababa'.
Cerință
Fiind dată o mulțime M, se cere să se determine lungimea maximă a unei subsecvențe care se găsește în toate șirurile din M.
Date de intrare
Pe prima linie a fișierului de intrare subsecvente.in se găsește un număr natural n egal cu cardinalul mulțimii M. Pe fiecare din următoarele n linii se găsește câte un șir din mulțimea M.
Date de ieșire
Pe prima linie a fișierului de ieșire subsecvente.out se va scrie un singur număr natural egal cu lungimea subsecvenței găsite
Exemplu:
Date de Intrare:
4
abbabaaaaabb
aaaababab
bbbbaaaab
aaaaaaabaaab
Date de Iesire:
5
Explicatie:
Lungimea unei subsecvenţe comune de lungime maximă este 5.
În exemplu subsecvența comună de lungime 5 este aaaab:
abbabaaaaabb, aaaababab, bbbbaaaab, aaaaaaabaaab.
Imi puteti da niste sfaturi despre aceasta problema, ce metode se pot folosi, si care sunt acestea?
|
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena