（その気持ちが）わかる
ハッシュ嫌ってきたので
問題
yukicoder contest 364 (Do you know Cherry Contest?) F No.2102 [Cherry Alpha *] Conditional Reflection
典型ライブラリ
- Suffix Array , Longest Common Prefix array
解説
「 1 文字だけ異なる」の判定方法
長さ $L$ （一定）の文字列 $S_i$ がたくさん与えられます。「 $S_i$ と $S_j$ は互いに、 $p$ 文字目以外が一致している（ $p$ 文字目は問わない）」が成り立つような組 $(i,j,p)$ の個数を計算してください。
$p$ を固定すると、各文字列を適切に $p$ 文字回転した後に $\text{LCP}(S_i,S_j)=L-1$ であるような組み合わせを数えることになります。ここで、 $S_1S_1S_2S_2\ldots$ のように連結した文字列のすべての接尾辞について、 $\text{LCP}$ が $L-1$ 以上であるようなグループに分類しておくと、すべての $p$ について同時に計算できます。このような分類は suffix array および lcp array を求めると簡単であり、 SA-IS を用いることで総文字数に対して線形時間になります。
分類
まず文字列長 $L$ で分類します。 $L=1,2$ は自明なので別で処理します。 $L\geq 3$ の場合は、次に、「 $1$ 文字だけ異なる」と同様の方法で、 $\text{LCP}$ が $L-2$ 以上であるようなグループに分類します。最後に、入れ替わっている $2$ 文字を非順序対とみて分類します。これにより、チェリーちゃんが反応してしまう十分条件で分類できました。
求解
反応する条件で分類したうち、最初に現れるもの以外を見たときには必ず反応します。どの分類グループでも最初に現れる場合、反応しません。これに従って出力を計算します。
各部分を改良すると、（総文字数に対する）線形時間にもできます。