Fișierul intrare/ieșire | subsecvente2.in, subsecvente2.out | Sursă | ad-hoc |
---|---|---|---|
Autor | Marius Stroe | Adăugată de | Cătălin Frâncu • Catalin.Francu |
Timp de execuție pe test | 2 sec | Limită de memorie | 8192 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Subsecvențe 2
Aceasta este o versiune cu limite mai grele a problemei Subsecvențe, propusă la OJI 2013, clasele 11-12.
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 subsecvente2.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 subsecvente2.out se va scrie un singur număr natural egal cu lungimea subsecvenței găsite.
Restricții
- 2 ≤ n ≤ 50
- Dacă |S| = |S1| + |S2| + ... + |Sn|, atunci |S| ≤ 500.000
- Se garantează că va exista întotdeauna soluție
- Se garantează că rezultatul nu va depăși 60
Exemplu
subsecvente.in | subsecvente.out |
---|---|
4 abbabaaaaabb aaaababab bbbbaaaab aaaaaaabaaab |
5 |
Explicație
Lungimea unei subsecvențe comune de lungime maximă este 5.
În exemplu subsecvența comună de lungime 5 este aaaab:
abbabaaaaabb, aaaababab, bbbbaaaab, aaaaaaabaaab.