Submission #47751847

---

Source Code Expand

#ABC329E Stamp

'''
前から決めるDPを行う。
DP[i][X]: S[0:i]まで正しい文字列になっていて(i文字目を決める直前で)、
          M-1文字前～1文字前のスタンプ状況がXにできるか？(True/False)

Xについて: 数字が小さい順にスタンプする(0ならスタンプしない)
(2,1,0): M-1文字目に最後にスタンプする

遷移: i文字目を書いてみて、これが一番上の文字になるかで遷移適否が決まる。
      遷移先の文字の組と、i文字目の種類を格納しておけば遷移ができる。
(2,1,0),0 : i文字目は塗らない
(3,1,0),2 : i文字目は2番目に塗る。2番目なのでi文字目は更新されない。
(2,1,0),3 : i文字目は3番目に塗る。i文字目は1文字目に変化する。

注意点として、i>N-M のときはスタンプが押せない(はみ出るため)。
'''

from itertools import permutations as pm

#入力受取  文字列を数列に置換('A'→0, 'Z'→25)
N,M=map(int,input().split())
S,T=[[ord(s)-ord('A') for s in input()] for _ in range(2)]

#M-1文字前から1文字前までの塗り方の列としてvalidなものを、tuple型でPに格納
P=set()
for d in range(M):  #塗る場所の個数
    for X in pm([i for i in range(1,d+1)]+[0]*(M-1-d)): P.add(X)

#P[i]=(a,b,c), Q[(a,b,c)]=i のように、Pをソートし圧縮。PとQで相互変換ができるように。
P=sorted(P); Q={j:i for i,j in enumerate(P)}

#P[i]からの(遷移先,遷移時のS[i]の文字) をRに格納する。
#i文字目には 0(塗らない),0.5(1の下に塗る), ･･･ , M-0.5(一番上に塗る)を考えればよい
R=[set() for _ in range(len(P))]
for pos,X in enumerate(P):
    for d in [0]+[i+0.5 for i in range(M)]:
        #M-1文字前から0文字前、つまりS[i]に影響を与える部分をYに全列挙する。
        #このうち最も値が大きい場所がS[i]の文字を決める。
        Y=list(X)+[d]; top=max(Y)
        if top==0: continue  #どこも塗らない場合は許容できないのでcontinue
        word=T[M-1-Y.index(top)]  #i文字目がどの文字になるか一意に定まる

        #Y[1:]を座標圧縮する。0を圧縮しない([1,2]→[0,1] にはしない)点に注意
        Y.pop(0); Z=sorted(set(Y+[0])); Z={j:i for i,j in enumerate(Z)}
        for i in range(M-1): Y[i]=Z[Y[i]]
        R[pos].add((Q[tuple(Y)],word))


#DP[i][X]: i文字目を塗る直前で、直近M-1文字の塗り方をXにできるか？
DP=[[False]*len(P) for _ in range(N+1)]
DP[0][Q[tuple([0]*(M-1))]]=True
for i in range(N):
    for X in range(len(P)):
        if DP[i][X]==False: continue
        if i<=N-M:  #スタンプを打っても盤外にはみ出ない場合
            for Y,word in R[X]:
                #S[i]==word すなわち スタンプ順を決定したときS[i]が正しくなれば遷移可能
                if S[i]==word: DP[i+1][Y]=True
        else:  #ここにスタンプが打てない場合
            for Y,word in R[X]:
                #追加条件として、末尾が0になることが必要。これは実際に変換すればわかる。
                if S[i]==word and P[Y][-1]==0: DP[i+1][Y]=True

#答えを出力
#DP[N]: S[0:N]が正しい文字列になっている状態 にどれかひとつでも到達できればYes
print('Yes' if any(DP[N]) else 'No')

Submission Info

Judge Result