ABC 401-500/ABC430E - Shift String - 競技プログラミング用 知識集積所【11/6更新】

---

問題

ABC430E

必要知識

B以下レベルの内容は省略

• Zアルゴリズム※

考え方

1文字ずつ後ろに回すことでBと同じ文字列にできるか、というのは、先頭から順に1文字ずつ末尾に付け加えたときに末尾がBになるかということと同じである。
それは、さらにいえば、Aの後ろにAを丸ごとくっつけて、途中にBが存在するようになるかという問題とも等しい。

ここまで来れば、あとは典型問題。
Zアルゴリズム※にB+「絶対に出現しない文字」+A+Aを渡せばよい。
「絶対に出現しない文字」より後ろで初めてB全体と一致するところを前から線形探索※し、最初に見つけたところがAの先頭にするべき文字の位置になる。

解答例

解答例

注意点

別解

• ローリングハッシュ※でもできる？

適当な数値を設定してBのローリングハッシュ※を計算したのち、A+Aの中でBと同じ長さのローリングハッシュ※を前から計算する。
同じ値のハッシュになったところが答え……の可能性が高い。
ハッシュの値をmod pで求めた場合、確率1/p程度で不当に一致をしてしまう。
今回の問題ではハッシュを1テスト当たり最大10^6回求めるため、10^9+7くらいの法だと1回くらい妙なことが起きる可能性は雑に見積もって10^(-3)程度はある。
2種類のハッシュを求めるとか、もっと大きな数を用いるとかでWA率を下げることはできるが、どこまで行っても確率的判定であり、100%ACできる解法にはならない。