Fișierul intrare/ieșire	sclm.in, sclm.out	Sursă	IQ Academy
Autor	teorie	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.05 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	1.5

Vezi soluțiile trimise | Statistici

Subșirul comun de lungime maximă (clasa a 7-a)

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.

Cerință

Să se determine subșirul de lungime maximă care apare atât în A cât și în B.

Date de intrare

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.

Date de ieșire

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. A doua linie va conține MAX numere ce reprezintă un subșir comun de lungime maximă pentru A si B.
• 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.

Restricții

• 1 ≤ M, N ≤ 1024
• Șirurile A și B conțin litere mari ale alfabetului englez

Exemplu

sclm.in	sclm.out
This is some text written on multiple lines.	This is another text written on multiple lines.

Explicație

...