[問題案] Repetition SubStrings about library-checker-problems HOT 5 OPEN

$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$

from library-checker-problems.

• 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 とほぼ同じ）．

from library-checker-problems.

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

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

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

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

from library-checker-problems.

ありがとうございます。

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

from library-checker-problems.

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

from library-checker-problems.