Fișierul intrare/ieșire subsecvente2.in, subsecvente2.out Sursă ad-hoc
Autor Marius Stroe Adăugată de avatar Catalin.Francu 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 stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 5 categorii