結果

問題 No.3638 Itsuki
コンテスト
ユーザー Tuchmos
提出日時 2026-08-25 15:52:54
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 1,211 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 287 ms
コンパイル使用メモリ 96,188 KB
実行使用メモリ 132,980 KB
最終ジャッジ日時 2026-08-25 15:53:11
合計ジャッジ時間 12,813 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
サンプル 0 % AC * 2
小課題1 10 % AC * 5
小課題2 50 % AC * 5 TLE * 1
小課題3 40 % AC * 17 TLE * 1
合計 10 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

##############################################
#https://atcoder.jp/contests/abc141/submissions/77328131

from random import randrange

MOD=(1<<61)-1
base=randrange(256,MOD-1)

def rolling_hash(s):
    n=len(s)
    hash_value=[0]*(n+1)
    power=[1]*(n+1)
    for i in range(n):
        power[i+1]=power[i]*base%MOD
        if isinstance(s[i],str):
            value=ord(s[i])+1
        else:
            value=s[i]+1
        hash_value[i+1]=(hash_value[i]*base+value)%MOD
    
    return hash_value,power

def get_hash(hash_value,power,left,right):
    return (hash_value[right]-hash_value[left]*power[right-left])%MOD

##############################################

N,Q=map(int,input().split())
S=list(input())
ans=[]
for _ in range(Q):
    q=list(input().split())
    if q[0]=='1':
        i,c=q[1:]
        i=int(i)-1
        S[i]=c
    else:
        t=q[1]
        h,p=rolling_hash(S)
        M=len(t)
        ht,_=rolling_hash(t)
        ok=False
        tar=ht[M]
        for l in range(N-M+1):
            hash=get_hash(h,p,l,l+M)
            if hash==tar:
                ok=True
                break
        ans.append('Yes' if ok else 'No')

import sys
sys.stdout.write('\n'.join(map(str,ans))+'\n')
0