Fişierul intrare/ieşire:	subsecvente2.in, subsecvente2.out	Sursă	OJI 2013, clasele 11-12
Autor	Marius Stroe	Adăugată de	Visan Radu •visanr
Timp execuţie pe test	0.15 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Subsecvente2

Fie n un numar natural si M={S₁, S₂, ..., S_n} o multime de siruri de caractere nevide. Fie S_k un sir de caractere din M. Atunci, orice caracter al lui S_k apartine multimii {'a', 'b'}. Notam prin |S_k| numarul caracterelor sirului S_k sau, echivalent, lungimea sa. O subsecventa S_k[i:j] a lui S_k este formata din caracterele situate pe pozitiile consecutive i, i+1, ..., j. Astfel, daca S_k = 'abbbaababa', atunci S_k[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| = |S₁| + |S₂| + ... + |S_n|, 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.in	subsecvente2.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

Cum se trimit solutii?