이렇게 생각했다

우선 s에서 t를 만들 수 있는 가장 짧은 장소를 찾는다. 예를 들어, 위 그림에서 abc는 (0-index로) 0,1,2 문자입니다. 이것은, t의 0문자째로부터 차례로 s를 탐색하면 알 수 있다. 예를 들어, s=axxbxxxc이고 t=abc라면 $[0,3,7]$가 된다. 여기서 먼저 거리의 max를 구해 둔다.

그런데, 다음에, t의 뒤의 문자에 해당하는 문자로부터, 가능한 한 뒤에 그 문자를 가져간다.

그림의 경우 c는 두 개의 후보가 있지만 두 번째 이동 후보가 더 멀기 때문에 그곳으로 이동합니다. 다음으로, b를 고려하면, 하나만 이동 목적지가 있기 때문에 (이것은 전혀 없을 수도 있음), 첫 번째 후보로 이동한다.
그런데, a는 3개의 이동처의 후보가 있지만, 순서를 유지해야 하기 때문에, 1번째의 후보 밖에 이동할 수 없다. (2,3번째로 이동해 버리면, bac나 bca가 되어 버린다)

이 동작은 각 문자 사이의 길이를 최대화하는 욕심을 찾는 것입니다.

구현

첫째로, 최단 위치는 선형으로 s를 탐구하거든 구한다. 이 때 가장 긴 거리를 기록합니다.
그런 다음 s의 각 문자를 선형으로 검사하고 특정 문자의 위치를 ​​저장합니다. 이것은, 큐 등으로 관리하면 되고, 큰 쪽으로부터 숫자를 취득할 수 있으면 된다.
그리고, t를 오른쪽에서 순서대로 보고, 최단의 위치로부터 한층 더 오른쪽으로 옮길 수 있는지를 큐로부터 위치를 취해 조사해 간다. 만약, 오른쪽으로 옮길 수 있는 경우, 그 거리가 최장의 거리가 되는지를 max로 취한다.

from collections import deque
def do():
    a2i = lambda x: ord(x) - ord("a")
    n, m = map(int, input().split())
    s = input()
    target = input()
    posAlphas = [deque([]) for _ in range(26)]
    # まず、最短を求める
    loc = [None] * m
    cur = 0
    for i in range(m):
        while s[cur] != target[i]:
            cur += 1
        loc[i] = cur
        cur += 1
    res = -1
    for i in range(m-1): # 最短の位置での最長の距離を調べる
        res = max(res, loc[i+1] - loc[i])
    curMax = 10 ** 9 # ひとつ大きい文字の位置(これを以上ではいけない)
    for i in range(n):
        val = a2i(s[i])
        posAlphas[val].append(i)
    for i in range(m-1, 0, -1): # 上からたどる
        # なるべく右に
        curLoc = loc[i] # 今の位置
        curChar = a2i(target[i]) # 今の文字
        while len(posAlphas[curChar]) > 0: #候補があるなら
            canPos = posAlphas[curChar].pop() # 一番大きいのを取る
            if curMax <= canPos:
                continue
            if canPos <= curLoc: # その文字と一緒なら
                break # 置き換えられないので抜ける
            loc[i] = canPos
            break
        curMax = loc[i] # tの次の文字はこれより右ではいけない
        res = max(res, loc[i] - loc[i - 1]) # 最長の距離を(必要なら)更新
    print(res)
do()