Najdlhší spoločný podreťazec

Dostali ste dva reťazce, nazvime ich A a B. Vašou úlohou je nájsť najdlhšiu spoločnú podpostupnosť, ktorú tieto dva reťazce zdieľajú.

Čo je to podpostupnosť? Predstavte si to takto: podpostupnosť sa vytvorí odstránením nula alebo viacerých znakov z reťazca bez zmeny poradia zostávajúcich znakov. Napríklad, "ace" je podpostupnosťou "abcde", ale "aec" nie je, pretože poradie 'e' a 'c' je zmenené.

Takže, pre dva reťazce A a B hľadáme najdlhší možný reťazec, ktorý možno vytvoriť odstránením znakov z A a tiež odstránením znakov z B.

Vstup

Na dvoch riadkoch vstupu dostanete reťazce A a B. Tieto reťazce sa skladajú len z malých znakov anglickej abecedy.

Výstup

Na jediný riadok výstupu vypíšte číslo -- dĺžku najdlhšieho spoločného podreťazca.

Príklad

logarithm
algorithm

7

Najdlhší podreťazec je lorithm: logarithm, algorithm.