ARC 024 C - だれじゃ

• 問題
• AC

「（部分列に）文字$c$がちょうど$x$個含まれること」の$26N$通りすべてに対して、あらかじめ乱数$R_{c, x}$を割り振っておく。 最初の$K$文字のヒストグラムを作って、各文字$c$について該当する$R_{c, x}$のXORを取って、最初のハッシュ値とする。

あとは、長さ$K$の部分列をスライドさせながら各部分列のハッシュ値を求めていく。直前の部分列のハッシュ値が$V$であったとし、文字$c$が加わって$c$の数が$x$から$x+1$に増え、文字$d$が除かれて$d$の数が$y$から$y-1$に減るとすると、新しい部分列のハッシュ値は$V \oplus R_{c, x} \oplus R_{c, x+1} \oplus R_{d, y} \oplus R_{d, y-1}$になる。このハッシュ値をキーとして、部分列の開始位置を保持しておく。同じハッシュ値が再び出現した時、開始位置が$K$以上離れていればアナグラムダジャレが見つかったことになる。

アルファベットのサイズを$\alpha$とするとき、計算量は${\mathcal O}(\alpha N)$。

---

こんなことしなくても、普通にヒストグラムをキーにするだけで通った……