Submission #47768714

---

Source Code Expand

#ABC329E Stamp

#Z-algorithm  TとS[i:]のLCP判定は、T+'$'+S のようにSに出ない文字を挟んで実行するとよい
#Reference: https://tjkendev.github.io/procon-library/python/string/z-algorithm.html
def Z_algorithm(S):  #SとS[i:]の最長共通接頭辞を求める
    N=len(S); A=[0]*N; i,j=1,0; A[0]=L=N
    while i<L:
        while i+j<L and S[j]==S[i+j]: j+=1
        if not j: i+=1; continue
        A[i]=j; k=1
        while L-i>k<j-A[k]: A[i+k]=A[k]; k+=1
        i+=k; j-=k
    return A

#入力受取
N,M=map(int,input().split()); S=input(); T=input()

#Tとの接頭辞長(Longest Common Prefix)をFrontに格納
Front=Z_algorithm(T+'#'+S)[M+1:]

#Tとの接尾辞長(Longest Common Suffix)をBackに格納。文字列反転してZ-Algoでよい。
Back=Z_algorithm(T[::-1]+'#'+S[::-1])[:M:-1]

#prefix combo/suffix comboで文字を消す  消せたらTrueにする
Left=[0]*N

#操作1: prefixを連続して取りのぞき、最後はT[0:M]を取り除くコンボが可能なのは？
#T: ABCD のとき、S: ABC AB ABCD は前からのスタンプ位置特定で消せる、みたいなイメージ
#尺取法で除去を行う。prefix comboの始点がLt  prefix comboで到達可能な限界がRt
Rt=0; cnt=0
for Lt in range(N):
    if Lt<cnt: continue  #考慮済み
    if Lt> Rt: cnt=Lt  #prefix comboを追い越してしまった場合。cntをリセット
    if Front[Lt]==0: continue  #無理
    Rt=max(Rt,Lt+Front[Lt])  #LCPはmaxを取ってよい。天才の発想
    if Front[Lt]==M:  #コンボが完成した場合
        for cnt in range(cnt,Rt): Left[cnt]=1

#操作2: suffixを連続で取り除く
#T: ABCD のとき、S: ABCD CD BCD は後ろから消せるイメージ。
Lt=N-1; cnt=N-1
for Rt in range(N-1,-1,-1):
    if cnt<Rt: continue
    if Lt> Rt: cnt=Rt
    if Back[Rt]==0: continue
    Lt=min(Lt,Rt-Back[Rt])
    if Back[Rt]==M:
        for cnt in range(cnt,Lt,-1): Left[cnt]=1
    
#以上の操作で残った文字列を考える。
#T: ABCD のとき、ABCD BC ABCD のように、末尾と先頭が切り取られたパターンがあり得る。
#この文字列たちがすべてTの連続部分列であればよい。
#さて、部分列は互いに距離Mずつ(ABCDのぶん)離れているので高々N/M個しかない。
#それぞれでO(M)かけて「Tの連続部分列に合致するか？」の判定を行えばよい。
#･･･ただし、少なくとも両端は除去できることが前提(コーナーケース: ABCB,ABC)。
if Left[0]&Left[-1]==0: print('No'); exit()
U=[]; Lt=0; Left.append(-1)
for Rt in range(N):
    if Left[Rt]==1: Lt=Rt+1; continue
    if Left[Rt+1]!=0: U.append((S[Lt:Rt+1],Rt+1-Lt))

#各Uに対してZ-algorithmを行う
for word,dist in U:
    result=Z_algorithm(word+'#'+T)  #Z-algorithm O(M)
    if max(result[dist+1:])<dist: print('No'); break  #だめな場所があればNo
else: print('Yes')  #全部部分列に合致した場合、Yesを出力


#ここからデバッグ用
def solve(N,M,S,T):
    #Tとの接頭辞長(Longest Common Prefix)をFrontに格納
    Front=Z_algorithm(T+'#'+S)[M+1:]

    #Tとの接尾辞長(Longest Common Suffix)をBackに格納。文字列反転してZ-Algoでよい。
    Back=Z_algorithm(T[::-1]+'#'+S[::-1])[:M:-1]

    #prefix combo/suffix comboで文字を消す  消せたらTrueにする
    Left=[0]*N

    #操作1: prefixを連続して取りのぞき、最後はT[0:M]を取り除くコンボが可能なのは？
    #T: ABCD のとき、S: ABC AB ABCD は前からのスタンプ位置特定で消せる、みたいなイメージ
    #尺取法で除去を行う。prefix comboの始点がLt  prefix comboで到達可能な限界がRt
    Rt=0; cnt=0
    for Lt in range(N):
        if Lt<cnt: continue  #考慮済み
        if Lt> Rt: cnt=Lt  #prefix comboを追い越してしまった場合。cntをリセット
        if Front[Lt]==0: continue  #無理
        Rt=max(Rt,Lt+Front[Lt])  #LCPはmaxを取ってよい。天才の発想
        if Front[Lt]==M:  #コンボが完成した場合
            for cnt in range(cnt,Rt): Left[cnt]=1

    #操作2: suffixを連続で取り除く
    #T: ABCD のとき、S: ABCD CD BCD は後ろから消せるイメージ。
    Lt=N-1; cnt=N-1
    for Rt in range(N-1,-1,-1):
        if cnt<Rt: continue
        if Lt> Rt: cnt=Rt
        if Back[Rt]==0: continue
        Lt=min(Lt,Rt-Back[Rt])
        if Back[Rt]==M:
            for cnt in range(cnt,Lt,-1): Left[cnt]=1
        
    #以上の操作で残った文字列を考える。
    #T: ABCD のとき、ABCD BC ABCD のように、末尾と先頭が切り取られたパターンがあり得る。
    #この文字列たちがすべてTの連続部分列であればよい。
    #さて、部分列は互いに距離Mずつ(ABCDのぶん)離れているので高々N/M個しかない。
    #それぞれでO(M)かけて「Tの連続部分列に合致するか？」の判定を行えばよい。
    #･･･ただし、少なくとも両端は除去できることが前提(コーナーケース: ABCB,ABC)。
    if Left[0]&Left[-1]==0: return 0
    U=[]; Lt=0; Left.append(-1)
    for Rt in range(N):
        if Left[Rt]==1: Lt=Rt+1; continue
        if Left[Rt+1]!=0: U.append((S[Lt:Rt+1],Rt+1-Lt))

    #各Uに対してZ-algorithmを行う
    for word,dist in U:
        result=Z_algorithm(word+'#'+T)  #Z-algorithm O(M)
        if max(result[dist+1:])<dist: return 0; break  #だめな場所があればNo
    else: return 1  #全部部分列に合致した場合、Yesを出力

def solve2(N,M,S,T):
    S=S+'#'

    #DP[i][j]: S[i]をT[j]で塗る状態にできるか？
    DP=[[False]*M for _ in range(N)]
    if S[0]==T[0]: DP[0][0]=True

    #DPを回す  DP[i][M-1]=True のときは、S[i+1]は(上書きされたスタンプが出てくる形で)
    #T[0:j]のどれかを押せると考え遷移する
    for i in range(N):
        for j in range(M):
            if DP[i][j]==False: continue
            if j <M-1:
                if S[i+1]==T[j+1]: DP[i+1][j+1]=True
            if j==M-1:  #隠し押ししていたスタンプの遷移
                for k in range(M):
                    if S[i+1]==T[k]: DP[i+1][k]=True
        #DP[i]のどれかひとつでもTrueなら、i+1を起点にスタンプが押せる
        if any(DP[i]) and S[i+1]==T[0]: DP[i+1][0]=True

    #Sの右端をスタンプの右端に合わせられる、すなわち S[-1]をT[-1]で押す ことができればYes
    return DP[-1][-1]

#ランダムテスト用
do_rantes=0
from random import randint as ri
if do_rantes:
    for _ in range(1000000):
        N=ri(2,15); M=ri(2,min(N,5))
        S=''.join([chr(ri(0,3)+ord('A')) for _ in range(N)])
        T=''.join([chr(ri(0,3)+ord('A')) for _ in range(M)])
        if solve(N,M,S,T)!=solve2(N,M,S,T): print(N,M,S,T)

Submission Info

Judge Result