Codeforces Round#704 C. Maximum width

こう考えた

まず最初、sの中でtを作れる最短の場所を探す。例えば、上の図でabcは(0-indexとして)0,1,2文字目である。これは、tの0文字目から順番にsを探索すればわかる。例えば、s=axxbxxxcでt=abcなら、$[0,3,7]$となる。ここでまず距離のmaxを求めておく。

さて、次に、tの後ろの文字にあたる文字から、なるべく後ろにその文字を持っていく。

図の場合、cは2つの候補があるが、2つ目の移動候補の方が遠いので、そちらに移動する。次に、bを考えると、1つしか移動先がない（これは全くないこともあり得る）ので、1つ目の候補に移動する。
さて、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()