== include(page="template/taskheader" task_id="sclm") ==
Fie *S* un șir de litere. Se numește subșir de lungime *K* al șirului *S* un nou șir *S*' = ([*S[~i~]*], *S[~i+1~]*, ... *S[~i+K-1~]*). De exemplu, șirul *S* = XYXZZ conține ca subșiruri șirurile YXZ sau XYX, dar nu conține subșirul YZ. Se dau două șiruri *A* și *B* ce conține litere mari ale alfabetului englez.
Fie *S* un șir de litere. Se numește subșir de lungime *K* al șirului *S* un nou șir *S*' = ([*S[~i~]*], *S[~i+1~]*, ... *S[~i+K-1~]*). De exemplu, șirul *S* = XYXZZ conține ca subșiruri șirurile YXZ sau XYX, dar nu conține subșirul YZ. Se dau două șiruri *A* și *B* ce conțin litere mari ale alfabetului englez.
h2. Cerință
Să se determine subșirul de lungime maximă care apare atât în *A* cât și în *B*.
h2. Date de intrare
Fișierul de intrare $sclm.in$ ...
Fișierul de intrare $sclm.in$ conține pe prima linie *M* și *N*, numărul de elemente pentru șirul *A*, respectiv pentru *B*. A doua linie conține *M* litere mari, elementele șirului *A*. A treia linie conține descrierea șirului *B* sub același format.
h2. Date de ieșire
În fișierul de ieșire $sclm.out$ ...
Fișierul de ieșire $sclm.out$ va conține pe prima și singura linie trei numere, despărțite prin spații: *MAX* *I[~A~]* *I[~B~]*, astfel:
* *MAX* - lungimea maximă a unui subșir comun.
* *I[~A~]* indicele apariției primei litere din subșirul comun în șirul *A*.
* *I[~B~]* indicele apariției primei litere din subșirul comun în șirul *B*.
Dacă există mai multe soluții se poate afișa oricare.
h2. Restricții
* $... ≤ ... ≤ ...$
* 1 ≤ *M*, *N* ≤ 1024
* Șirurile *A* și *B* conțin litere mari ale alfabetului englez.
* Se garantează că șirurile *A* și *B* au în comun cel puțin o literă.
* Indicii literelor șirurilor se numerotează începînd cu 1.
h2. Exemplu
table(example).
|_. sclm.in |_. sclm.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
|_. sclm.in |_. sclm.out |_. Explicație |
| 5 7
ABCBB
BBCBCBA
| 3 2 4
| Subșirul maximal are lungime 3. El este *BCB* și pornește la poziția 2 în șirul *A*
și la poziția 4 în șirul *B*.
O soluție alternativă putea fi 3 2 2.
|
== include(page="template/taskfooter" task_id="sclm") ==
