Fişierul intrare/ieşire:subsecvente.in, subsecvente.outSursăOJI 2013, Clasele 11-12
AutorMarius StroeAdăugată decocoClaudiu coco
Timp execuţie pe test0.6 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Subsecvente

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.insubsecvente.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 sa te autentifici pentru a trimite solutii. Click aici