Fișierul intrare/ieșire | subsecvente.in, subsecvente.out | Sursă | OJI 2013, Clasele 11-12 |
---|---|---|---|
Autor | Marius Stroe | Adăugată de | Claudiu • coco |
Timp de execuție pe test | 0.6 sec | Limită de memorie | 131072 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Subsecvente (clasele 11 și 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 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.
Restricții
- 1 < n < 5
- Dacă |S| = |S1| + |S2| + ... + |Sn|, atunci |S| < 50.001
- Se garantează că va exista întotdeauna soluție
- Se garantează că rezultatul nu va depăși 60
- Pentru 30% din teste: |S| < 101
- Pentru 55% din teste: |S| < 3.501
- Pentru 80% din teste: |S| < 10.001
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.