{-# LANGUAGE MultiParamTypeClasses, ScopedTypeVariables, ExplicitForAll,InstanceSigs,PackageImports #-}
import qualified Data.ByteString.Char8 as B

import Data.List
import Control.Monad.Primitive 
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as MV
import Data.Monoid((<>))
import Data.Function hiding ((&))
import Debug.Trace
import qualified Data.Vector.Generic as G
import Unsafe.Coerce
 
(&) :: a -> (a -> b) -> b
(&) a b = b a
 
infixl 1 &

newtype P' = P' { unP' :: P }

instance {-# Overlaps #-} G.Vector V.Vector P where
    {-# INLINE basicUnsafeFreeze #-}
    basicUnsafeFreeze :: forall m. PrimMonad m => MV.MVector (PrimState m) P -> m (V.Vector P)
    basicUnsafeFreeze v = unsafeCoerce (G.basicUnsafeFreeze (unsafeCoerce v :: MV.MVector (PrimState m) P') :: m (V.Vector P'))
    {-# INLINE basicUnsafeThaw #-}
    basicUnsafeThaw v = fmap unsafeCoerce $ G.basicUnsafeThaw (unsafeCoerce v :: V.Vector P') 
    {-# INLINE basicLength #-}
    basicLength v = G.basicLength (unsafeCoerce v :: V.Vector P')
    {-# INLINE basicUnsafeSlice #-}
    basicUnsafeSlice offset len v = unsafeCoerce $ G.basicUnsafeSlice offset len (unsafeCoerce v :: V.Vector P')
    {-# INLINE basicUnsafeIndexM #-}
    basicUnsafeIndexM v i = fmap unsafeCoerce $ G.basicUnsafeIndexM (unsafeCoerce v :: V.Vector P') i
    {-# INLINE basicUnsafeCopy #-}
    basicUnsafeCopy :: forall m. PrimMonad m => MV.MVector (PrimState m) P -> V.Vector P -> m ()
    basicUnsafeCopy dst src = G.basicUnsafeCopy (unsafeCoerce dst :: MV.MVector (PrimState m) P') (unsafeCoerce src :: V.Vector P')
    {-# INLINE elemseq #-}
    elemseq _ (P i x) b = x `seq` b

 
data P = P { p_fst :: {-# UNPACK #-} !Int, 
             p_snd :: (String -> String) }
 
instance Eq P where
    (==) = (==) `on` p_fst
instance Ord P where
    compare = compare `on` p_fst
instance Monoid P where
    mappend (P a b) (P c d) = P (a + c) (b . d)
    mempty = P 0 id 
 
main :: IO ()
main = do
    s <- B.getLine
    t <- B.getLine
    let len_s = B.length s
        result = B.foldl' step s0 t
        v_end = result `seq` traceShow "v_end" (result & V.last & p_snd & ("" &))
        step :: V.Vector P -> Char -> V.Vector P
        step tbl ch = tbl'
            where
            tbl' = G.constructN (len_s + 1) gen 
            gen vec | i == 0 = mempty
                    | ch == ch' = a1 `max` a2 `max` a3
                    | otherwise = a1 `max` a2
                where
                    i = V.length vec
                    ch' = B.index s (i - 1)
                    a1 = V.last vec
                    a2 = tbl V.! i
                    a3 = tbl V.! (i - 1) <> (P 1 (ch:))
        s0 = V.replicate (len_s + 1) mempty
    putStrLn (v_end :: String)
