subsecvente
Fie n
un număr natural și \(M=\){
\(S_1,S_2,…,S_n\)}
o mulțime de șiruri de caractere nevide. Fie \(S_k\) un șir de caractere din M
. Atunci, orice caracter al lui \(S_k\) aparține mulțimii { 'a', 'b' }
. Notăm prin \(|S_k|\) numărul caracterelor șirului \(S_k\) sau, echivalent, lungimea sa. O subsecvență \(S_k[i:j]\) a lui \(S_k\) este formată din caracterele situate pe pozițiile consecutive i, i+1, ..., j
. Astfel, dacă \(S_k = abbbaababa\), atunci \(S_k[3:6] = bbaa\) sau subsecvența evidențiată: abbbaababa.
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
.
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
.
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.
1 < n < 5
|S| < 50 001
60
30%
din teste: |S| < 101
55%
din teste: |S| < 3 501
80%
din teste: |S| < 10 001
subsecvente.in
4
abbabaaaaabb
aaaababab
bbbbaaaab
aaaaaaabaaab
subsecvente.out
5
Lungimea unei subsecvenţe comune de lungime maximă este 5
.
În exemplu subsecvența comună de lungime 5
este aaaab
:
abbabaaaaabb, aaaababab, bbbbaaaab, aaaaaaabaaab.
ID: 36
Upload: liviu
Input: subsecvente.in/subsecvente.out
Memory limit: 128MB/64MB
Time limit: 0.2s
Author: Marius Laurențiu Stroe
Source: OJI 2013 XI-XII: Problema 2