ABC477 C - Range Search Query
- サイト
- AtCoder
- コンテスト
- ABC477
- 問題
- C - Range Search Query
- 難易度
- 456
文字列 が与えられます。 個のクエリ それぞれについて、 の 文字目から 文字目までの部分に が含まれるかを判定する問題です(、、)。
の 文字目から 文字目までに が含まれるのは、 が の 文字目から始まって出現するような が の範囲にあるときです。
そこで、前処理として の各位置から が始まるかを調べておきます。 なので、各位置で愚直に比べても で間に合います。これの累積和をとっておけば、各クエリでは区間 にある開始位置の個数が で求まり、それが 以上なら Yes です。
Python
Q = int(input())S = input()T = input()N, M = len(S), len(T)acc = [0] * (N + 1)for i in range(N): acc[i + 1] = acc[i] + S.startswith(T, i)for _ in range(Q): L, R = map(int, input().split()) print("Yes" if L - 1 <= R - M and acc[R - M + 1] > acc[L - 1] else "No")acc[i] は、 の出現のうち開始位置(0 始まり)が 未満のものの個数です。0 始まりで開始位置が 以上 以下の出現があるかを、acc[R - M + 1] > acc[L - 1] で調べています。 のときは区間が空なので、先に L - 1 <= R - M で除いています。
Uiua
⋅◌⍥◡(&p⨬"No""Yes">0/-⬚0⊏-:⊜⋕⊸≠@ &sc):⊙:[2⧻]⟜(\+⌕)&sc&sc⋕&sc⋕&sc で 、続く 2 つの &sc で と を読みます。
⟜(\+⌕) では、⌕ で の各位置から が始まるかの 0/1 の列を作り、\+ で累積和 にします。 は開始位置(0 始まり)が 以下の出現の個数です。⟜ で を残しておき、[2⧻] で を作ります。:⊙: で並べ替えて、 の下に と が来るようにしています。
⍥◡(…) で、 と を残したまま中の処理を 回繰り返します。中の処理は次のとおりです。
⊜⋕⊸≠@ &scでクエリを読んで にします。-:で を計算します。⬚0⊏で からこの 2 か所を取り出し、/-で を求めます。これが区間内にある開始位置の個数です。 のときの添字 は、⬚0で として扱っています。>0で 個以上あるかを判定し、⨬"No""Yes"で文字列を選んで&pで出力します。
最後の ⋅◌ で、残しておいた と を捨てています。