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 $ とすると、
\[ \sum_{l = 1}^{x} \sum_{r = l}^{x} (r - l + 1) = \frac{ x ( x + 1) (x + 2) } {6} \]
となります。
実装では、区間内の文字をランレングス圧縮し、queueに積んでいくなどするとよいです。(文字がないときの処理に注意)
計算量は、各文字について高々定数回しか見ないので、$ \Theta ( \sum |S| ) $ となります。