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 dintre 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
Exemple
subsecvente.in
subsecvente.out
Explicaţii
4
abbabaaaaabb
aaaababab
bbbbaaaab
aaaaaaabaaab
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.