Fişierul intrare/ieşire:subsecvente2.in, subsecvente2.outSursăOJI 2013, clasele 11-12
AutorMarius StroeAdăugată devisanrVisan Radu visanr
Timp execuţie pe test0.3 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Subsecvente2

Fie n un numar natural si M={S1, S2, ..., Sn} o multime de siruri de caractere nevide. Fie Sk un sir de caractere din M. Atunci, orice caracter al lui Sk apartine multimii {'a', 'b'}. Notam prin |Sk| numarul caracterelor sirului Sk sau, echivalent, lungimea sa. O subsecventa Sk[i:j] a lui Sk este formata din caracterele situate pe pozitiile consecutive i, i+1, ..., j. Astfel, daca Sk = 'abbbaababa', atunci Sk[3:6] = 'bbaa' sau subsecventa evidentiata: 'abbbaababa'.

Cerinta

Fiind data o multime M, se cere sa se determine lungimea maxima a unei subsecvente care se gaseste in toate sirurile din M.

Date de intrare

Pe prima linie a fisierului de intrare subsecvente2.in se gaseste un numar natural n egal cu cardinalul multimii M. Pe fiecare dintre urmatoarele n linii se gaseste cate un sir din multimea M.

Date de ieşire

Pe prima linie a fisierului de iesire subsecvente2.out se va scrie un singur numar natural egal cu lungimea subsecventei gasite.

Restricţii

  • 1 < n < 5
  • Daca |S| = |S1| + |S2| + ... + |Sn|, atunci |S| < 50 001
  • Se garanteaza ca va exista intotdeauna solutie.
  • Se garanteaza ca rezultatul nu va depasi 60.
  • Pentru 30% din teste: |S| < 101
  • Pentru 55% din teste: |S| < 3 501
  • Pentru 80% din teste: |S| < 10 001

Exemplu

subsecvente2.insubsecvente2.out
4
abbabaaaaabb
aaaababab
bbbbaaaab
aaaaaaabaaab
5

Explicaţie

Lungimea unei subsecvente comune de lungime maxima este 5.
In exemplu subsecventa comuna de lungime 5 este aaaab:
abbabaaaaabb, aaaababab, bbbbaaaab, aaaaaaabaaab

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?