subsecvente

Time limit: 0.2s
Memory limit: 128MB
Input: subsecvente.in
Output: subsecvente.out

Fie n un număr natural și M={S1,S2,,Sn}M=\{S_1,S_2,…,S_n\} o mulțime de șiruri de caractere nevide. Fie SkS_k un șir de caractere din M. Atunci, orice caracter al lui SkS_k aparține mulțimii { 'a', 'b' }. Notăm prin Sk|S_k| numărul caracterelor șirului SkS_k sau, echivalent, lungimea sa. O subsecvență Sk[i:j]S_k[i:j] a lui SkS_k este formată din caracterele situate pe pozițiile consecutive i, i+1, ..., j. Astfel, dacă Sk=abbbaababaS_k = abbbaababa, atunci Sk[3:6]=bbaaS_k[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|S| = |S_1| + |S_2| + … + |S_n|, 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

4
abbabaaaaabb
aaaababab
bbbbaaaab
aaaaaaabaaab

subsecvente.out

5

Explicații

Lungimea unei subsecvenţe comune de lungime maximă este 5.

În exemplu subsecvența comună de lungime 5 este aaaab:
abbabaaaaabb, aaaababab, bbbbaaaab, aaaaaaabaaab.

Problem info

ID: 36

Editor: liviu

Author:

Source: OJI 2013 XI-XII: Problema 2

Tags:

OJI 2013 XI-XII

Log in or sign up to be able to send submissions!