コンテンツにスキップ

ABC477 C - Range Search Query

サイト
AtCoder
コンテスト
ABC477
問題
C - Range Search Query
難易度
456

文字列 S,TS, T が与えられます。QQ 個のクエリ (L,R)(L, R) それぞれについて、SS の LL 文字目から RR 文字目までの部分に TT が含まれるかを判定する問題です(∣S∣≤4×105|S| \le 4 \times 10^5、∣T∣≤10|T| \le 10、Q≤2×105Q \le 2 \times 10^5)。

SS の LL 文字目から RR 文字目までに TT が含まれるのは、TT が SS の ii 文字目から始まって出現するような ii が L≤i≤R−∣T∣+1L \le i \le R - |T| + 1 の範囲にあるときです。

そこで、前処理として SS の各位置から TT が始まるかを調べておきます。∣T∣≤10|T| \le 10 なので、各位置で愚直に比べても O(∣S∣∣T∣)O(|S||T|) で間に合います。これの累積和をとっておけば、各クエリでは区間 [L,R−∣T∣+1][L, R - |T| + 1] にある開始位置の個数が O(1)O(1) で求まり、それが 11 以上なら 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] は、TT の出現のうち開始位置(0 始まり)が ii 未満のものの個数です。0 始まりで開始位置が L−1L - 1 以上 R−∣T∣R - |T| 以下の出現があるかを、acc[R - M + 1] > acc[L - 1] で調べています。R−L+1<∣T∣R - L + 1 < |T| のときは区間が空なので、先に L - 1 <= R - M で除いています。

Uiua
⋅◌⍥◡(&p⨬"No""Yes">0/-⬚0⊏-:⊜⋕⊸≠@ &sc):⊙:[2⧻]⟜(\+⌕)&sc&sc⋕&sc

⋕&sc で QQ、続く 2 つの &sc で SS と TT を読みます。

⟜(\+⌕) では、⌕ で SS の各位置から TT が始まるかの 0/1 の列を作り、\+ で累積和 PP にします。PkP_k は開始位置(0 始まり)が kk 以下の出現の個数です。⟜ で TT を残しておき、[2⧻] で [2,∣T∣][2, |T|] を作ります。:⊙: で並べ替えて、QQ の下に [2,∣T∣][2, |T|] と PP が来るようにしています。

⍥◡(…) で、[2,∣T∣][2, |T|] と PP を残したまま中の処理を QQ 回繰り返します。中の処理は次のとおりです。

  1. ⊜⋕⊸≠@ &sc でクエリを読んで [L,R][L, R] にします。
  2. -: で [L,R]−[2,∣T∣]=[L−2,R−∣T∣][L, R] - [2, |T|] = [L - 2, R - |T|] を計算します。
  3. ⬚0⊏ で PP からこの 2 か所を取り出し、/- で PR−∣T∣−PL−2P_{R - |T|} - P_{L - 2} を求めます。これが区間内にある開始位置の個数です。L=1L = 1 のときの添字 −1-1 は、⬚0 で 00 として扱っています。
  4. >0 で 11 個以上あるかを判定し、⨬"No""Yes" で文字列を選んで &p で出力します。

最後の ⋅◌ で、残しておいた [2,∣T∣][2, |T|] と PP を捨てています。