lcs.py

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# Template di soluzione di lcs

from __future__ import print_function, division
import sys
from functools import lru_cache

if sys.version_info < (3, 0):
    input = raw_input  # in python2, l'equivalente di input è raw_input


########################################################
# INIZIO area entro la quale ti richiediamo/consigliamo di operare.

@lru_cache(None)
def lcs(s, t):
    # Caso base
    if len(t) == 0:
        return 0

    """
    Se osservo il primo carattere della stringa 't' ci sono due casi:
      1) La sottostringa comune più lunga contiene questo carattere
      2) Oppure non lo contiene
      
    Nel caso 1 devo shiftare a sinistra la stringa 's' fino a quando il suo primo carattere non è uguale al primo
    carattere di 't'. A questo punto devo "tagliare" via i primi caratteri di entrambe le stringhe e risolvere il
    sottoproblema così individuato.
    
    Nel caso 2 invece "taglio" via il primo carattere di 't' e risolvo il sottoproblema.
    
    Ad ogni passo, provo entrambe le situazioni (quando possibile) e considero quella che restituisce output più grande.
    Si noti che nel caso 1 posso sto, in un certo senso, aggiungendo un carattere alla sottostringa individuata. Per
    questo che faccio +1 al risultato del sottoproblema.
    """

    # Di quanto devo shiftare 's' per fare in modo che 's[0] == t[0]'? Questo è ciò che metto in 'boundary'. Se è 'None'
    # significa che la stringa 's' non contiene 't[0]' e quindi il caso 1 non è applicabile.
    boundary = next(filter(lambda i: s[i] == t[0], range(len(s))), None)
    return max(lcs(s, t[1:]), 1 + lcs(s[boundary+1:], t[1:]) if boundary is not None else 0)


# FINE area entro la quale ti richiediamo/consigliamo di operare.
########################################################

len_s, len_t = map(int, input().split())
s = input()
t = input()
# print(f"{len_s} {len_t}")
# print(f"s={s}")
# print(f"t={t}")
print(lcs(s, t))