{-# LANGUAGE BangPatterns #-}
import qualified Data.ByteString.Char8 as B
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as UV

main=B.interact $ B.pack.g.take 2.B.lines
g [!s,!t]=mk "" (ls-1) (lt-1) where
    ls = B.length s
    lt = B.length t
    rd si ti = (aa V.! si) UV.! ti
    mk !as si ti
        | si<0 || ti<0 = as
        | B.index s si == B.index t ti = mk (B.index s si : as) (si-1) (ti-1)
        | rd (si+1) ti > rd si (ti+1) = mk as si (ti-1)
        | otherwise = mk as (si-1) ti
    bb :: V.Vector (UV.Vector Int)
    bb = V.constructN (ls+1) mi where
        mi vi | i==0 = UV.replicate (lt+1) 0 | otherwise = UV.constructN (lt+1) mj where
            i = V.length vi
            mj vij |j==0 = 0 | otherwise = if B.index s (i-1) == B.index t (j-1)
                then 1 + V.last vi UV.! (j-1)
                else max (UV.last vij) (V.last vi UV.! j)
                where j = UV.length vij
