yukicoder No.962 LCPs
想定解と違ったので一応。
まず、文字列を横に区切って考える(1文字目の列, 2文字目の列, ...のように)。すると、求める値は、
\[ \displaystyle \sum_{i = 1}^{ max(|S|) } \sum _ {L = 1}^{N} \sum _ {R = L}^{N} ( S _ L, S _ {L+1}, \cdots , S _ R の i 文字目までが一致する ? R-L+1 : 0) \]
となる。 文字列を下のようにグループ分けする。(列ごとに、$$ i $$ 文字目まで一致するグループに分割していく)
すると、このグループ内の連続部分列全てが $$ i $$文字目まで一致することになる。
よって、このグループ分けができれば、グループごとに、「長さに応じた値」を足し合わせればよい。
この「長さに応じた値」は、長さを $$ x $$ とすると、
\[ \displaystyle \sum _ {l = 1}^{x} \sum _ {r = l}^{x} (r - l + 1) = \frac{ x ( x + 1) (x + 2) } {6} \]
になる。
実装のほうだが、区間内の文字をランレングス圧縮し、queueに積んでいくなどするとよい。(文字がないときの処理に注意)
計算量は、各文字について高々定数回しか見ないので、$$ \Theta ( \sum |S| ) $$ となる。
