{-# LANGUAGE BangPatterns #-}
import           Control.Monad
import           Data.Array.ST
import           Data.Array.Unboxed    (UArray)
import qualified Data.Array.Unboxed    as U
import qualified Data.ByteString.Char8 as BS
import           Data.List

getAsCharArray1DWithLength :: IO (Int, UArray Int Char)
getAsCharArray1DWithLength = BS.getLine >>= \cs ->
  let !n = BS.length cs
      !ary = (U.listArray (1,n) $ unfoldr BS.uncons cs) :: UArray Int Char
  in return (n, ary)

main :: IO ()
main = do
  (!n,!sa) <- getAsCharArray1DWithLength
  (!m,!ta) <- getAsCharArray1DWithLength
  let !result = solve (n,sa) (m,ta)
  putStrLn $ restore sa result n m

solve :: (Int, UArray Int Char) -> (Int, UArray Int Char) -> UArray (Int,Int) Int
solve (!n',!sa) (!m',!ta) = runSTUArray $ do
  !dp <- newArray ((0,0),(n',m')) 0
  forM_ [(n_,m_) | !n_ <- [1..n'], !m_ <- [1..m']] $ \(!n,!m) -> do
    !a <- readArray dp (n-1,m-1)
    !b <- readArray dp (n,m-1)
    !c <- readArray dp (n-1,m)
    if sa U.! n == ta U.! m
      then writeArray dp (n,m) $ maximum [a+1,b,c]
      else writeArray dp (n,m) $ maximum [b,c]
  return dp

restore :: UArray Int Char -> UArray (Int,Int) Int -> Int -> Int -> String
restore !st !ary !n !m = go n m ""
  where go 0 _ !ss = ss
        go _ 0 !ss = ss
        go !i !j !ss
          | ary U.! (i,j) == ary U.! (i-1,j) = go (i-1) j ss
          | ary U.! (i,j) == ary U.! (i,j-1) = go i (j-1) ss
          | otherwise                        = go (i-1) (j-1) ((st U.! i):ss)
