[問題案] Repetition SubStrings

[halc-git]

問題名: Repetition SubStrings(もっといい名前はありそう)

問題文

長さ $N$ の文字列 $S$ と、長さ $M$ の文字列 $T$ が与えられます。

以下の形式のクエリを $Q$ 回処理してください。

• $a,b,c,d,e,f$ : $S$ の $a$ 文字目から $b-1$ 文字目までを $c$ 回繰り返した文字列と、 $T$ の $d$ 文字目から $e-1$ 文字目までを $f$ 回繰り返した文字列が、一致していればYes、でなければNoを出力する。( $a,b,d,e$ は 0-indexed )

制約

• $1 \leq N,M \leq 5\times 10^5$
• $1 \leq Q \leq 5\times 10^5$
• $S,T$ はいずれも英小文字からなる
• $0 \leq a \lt b \lt N$
• $0 \leq d \lt e \lt M$
• $1 \leq c,f \leq 10^9$

入力

N
S
T
Q
query_0
query_1
\vdots
query_{N-1}

解法

ロリハでがんばる想定です。純粋なロリハをverifyできる問題はなさそうだと思って提案します(あったらすみません)

繰り返しは $O(\log N)$ で高速にできるはずなので計算量は $O(N+Q \log \max(c,f))$ になると思います。

メモ

$c=f=1$ のケースを多めに入れたいです。

[maspypy]

• repetition 要素について
  $a^c=b^d$ となるのは， $c,d$ が互いに素な場合に帰着したあと $a=s^d$, $b=s^c$ と書けるかの判定にできて，$a, b$ の prefix や suffix を適切に比較するだけでできるので，ほとんど $c=d=1$ 以上と同じことになります．この処理を問いたいという主旨の問題ならばそれでもよいですが，そうではなければ repetition 要素は無駄だと思います．

• Rolling Hash 解法について
  長さ $n$ の文字列に対する衝突確率の評価は， $O(n/p)$ となります．例えば，同一の文字列が $p-1$ 個続くパターン aaa...aaa や bbb...bbb のハッシュはほとんどの base で $0$ となり，これらは $p$ を法とする Rolling Hash では区別されません．この点は考慮していますか？

---

純粋なロリハをverifyできる問題

というのがどのような意味を指しているか分かりませんが，

Z Algorithm：Rolling Hash で lcp を計算
Enumerate Palindromes：Rolling Hash で回文判定＋二分探索
Suffix Array：Rolling Hash で suffix の比較関数を作ってソート

などの解法があって，利用しているユーザーはいます．

Rolling Hash が解法に使えることが，今以上に分かりやすい問題が欲しいという意味であれば，単に $S[a:b] = S[c:d]$ であるか否かをクエリする問題を置くというのはありえると思います．
あるいは（Repetition のように）Hash が結合可能であるという点を問いたいということであれば，文字列に変更クエリも与えて Rolling Hash をセグメント木に乗せるような設定を考える方が良いかもしれません（ただしこれは point_set_range_composite とほぼ同じ）．

[halc-git]

aaa...aaaやbbb...bbbのハッシュはほとんどの base で $0$ となり，これらは $p$ を法とする Rolling Hash では区別されません．この点は考慮していますか？

$p$ を $2^{31}-1$ や $2^{61}-1$ などの大きな素数でとりbaseを複数用意するローリングハッシュであれば制約内で衝突する確率は無視できるはずです。その辺も考慮したら実行制限時間は多めに取るべきかなとは思っています。

Rolling Hash が解法に使えることが，今以上に分かりやすい問題が欲しいという意味であれば，

説明不足でした。この意味です。
確かに部分文字列だけで十分かもしれません。

[maspypy]

$p$ を $2^{31}−1$ や $2^{61}−1$ などの大きな素数でとりbaseを複数用意するローリングハッシュであれば制約内で衝突する確率は無視できるはずです。

文字列長が $10^{14}$ 以上になるので，特に前者は保証がないと思います（base をいくつ用意してもダメであることはありうると思います）．ただし、同じ文字列の繰り返しという形に限定すれば実は正当とかはあるかもしれません．

---

とりあえずこんな感じで考えます．

長さ $N$ の文字列 $S$ が与えられます。以下の形式のクエリを $Q$ 回処理してください。

- $a, b, c, d$：$S_a\cdots S_{b-1}$ と $S_{c}\cdots S_{d-1}$ の一致判定をせよ。

制約
- $1\leq N \leq 10^6$, $1\leq Q\leq 10^6$
- $0\leq a\leq b\leq N$, $0\leq c\leq d\leq N$

[halc-git]

ありがとうございます。

(さっきの文章を書いてる時点で繰り返しのことが頭から抜けててすこしおかしなことを書いていました…)

[maspypy]

ありがとうございます。
部分文字列一致判定クエリでお願いします。