問題
文字列$S$（長さ$N$）が与えられる。$S$に含まれる相異なる部分文字列すべてについて、その長さの総和を求めよ。
例えば$S=$"aab"のとき、相異なる部分文字列はa, aa, aab, ab, bの5個で、長さの総和は$1+2+3+2+1=9$である。
入力形式
S制約
$1 \le |S| \le 5\times10^5$
$S$は英小文字のみ
入出力例
入力例1
aab出力例1
9入力例2
aaaa出力例2
10概念図
ヒント（段階的開示）
ヒント1（方向性）
SAMの各状態(初期状態を除く)は「長さの区間$(\text{len}[\text{link}[v]],\text{len}[v]]$」に対応する部分文字列の集合を表す。今回は個数ではなく「長さの総和」を求める点が違う。
ヒント2（アプローチ）
状態$v$が表す部分文字列の長さは$\text{len}[\text{link}[v]]+1,\dots,\text{len}[v]$のちょうど1つずつに対応する。その寄与は等差数列の和$\sum_{k=\text{len}[\text{link}[v]]+1}^{\text{len}[v]}k$になる。
ヒント3（誘導）
等差数列の和の公式$\sum_{k=a+1}^{b}k=\frac{(a+b+1)(b-a)}{2}$（$a=\text{len}[\text{link}[v]]$, $b=\text{len}[v]$）を使う。SAMの構築は標準的なオンライン構築で$O(N)$。
def add_char(c):
global last
cur = new_state(len=states[last]['len'] + 1)
p = last
while p != -1 and c not in states[p]['trans']:
states[p]['trans'][c] = cur
p = states[p]['link']
...模範解答 (Python)
import sys
def build_sam(s):
MAXN = 2 * len(s) + 5
length = [0] * MAXN
link = [-1] * MAXN
trans = [dict() for _ in range(MAXN)]
size = 1
last = 0
length[0] = 0
link[0] = -1
for ch in s:
cur = size
size += 1
length[cur] = length[last] + 1
p = last
while p != -1 and ch not in trans[p]:
trans[p][ch] = cur
p = link[p]
if p == -1:
link[cur] = 0
else:
q = trans[p][ch]
if length[p] + 1 == length[q]:
link[cur] = q
else:
clone = size
size += 1
length[clone] = length[p] + 1
trans[clone] = dict(trans[q])
link[clone] = link[q]
while p != -1 and trans[p].get(ch) == q:
trans[p][ch] = clone
p = link[p]
link[q] = clone
link[cur] = clone
last = cur
return size, length, link
def main():
s = sys.stdin.readline().strip()
size, length, link = build_sam(s)
total = 0
for v in range(1, size):
a = length[link[v]]
b = length[v]
total += (a + b + 1) * (b - a) // 2
print(total)
main()Step-by-Step 解説
1SAMの状態が表す部分文字列集合
各状態$v$は同じendpos集合を持つ部分文字列たちの集まりを表し、その長さは$\text{len}[\text{link}[v]]+1$から$\text{len}[v]$までの連続区間を1回ずつカバーする。
各状態$v$は同じendpos集合を持つ部分文字列たちの集まりを表し、その長さは$\text{len}[\text{link}[v]]+1$から$\text{len}[v]$までの連続区間を1回ずつカバーする。
2個数から総和へ
標準の「個数」問題では$\text{len}[v]-\text{len}[\text{link}[v]]$を足すが、今回は区間に含まれる整数の総和を等差数列公式で$O(1)$計算し全状態を走査する。全体$O(N)$。
標準の「個数」問題では$\text{len}[v]-\text{len}[\text{link}[v]]$を足すが、今回は区間に含まれる整数の総和を等差数列公式で$O(1)$計算し全状態を走査する。全体$O(N)$。
3SAM構築のロジック
新状態curを作り、lastからlinkを辿りながら未定義の遷移にcurへのリンクを張る。既存の遷移に当たったらlenの一致でリンク先を決めるかクローンするか分岐する。
新状態curを作り、lastからlinkを辿りながら未定義の遷移にcurへのリンクを張る。既存の遷移に当たったらlenの一致でリンク先を決めるかクローンするか分岐する。
4クローン処理の意味
1状態=1連続長さ区間という不変量を保つため、区間を分割する必要がある場合にクローンを作る。
1状態=1連続長さ区間という不変量を保つため、区間を分割する必要がある場合にクローンを作る。
5計算量
状態数は高々$2N-1$個。$N=5\times10^5$では辞書使用の定数倍に注意が必要。
状態数は高々$2N-1$個。$N=5\times10^5$では辞書使用の定数倍に注意が必要。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 個数の公式をそのまま総和に使う | 「個数」と「長さの総和」を混同 | 等差数列の和$(a+b+1)(b-a)/2$を使う |
| 初期状態も加算してしまう | ループ範囲をrange(size)にする | 初期状態は寄与しないのでrange(1,size)にする |
| クローンのtransを浅いコピーでなく参照で共有 | trans[clone]=trans[q]で同じ辞書を共有 | trans[clone]=dict(trans[q])で必ずコピーする |
| linkの更新順序ミス | link[q]を先に上書きしてから元の値を使う | 代入と値の使用順序を混同しないよう注意する |
| 境界処理漏れ | N=1のケースをテストしない | 短い文字列でも状態数が正しいか確認する |
次のステップ
- 発展: 出現回数の総和(延べ出現数×長さ)を求める場合、endposサイズをparent tree上のDPで求めてから同様に集計せよ。
- 発展2: 複数文字列の共通部分文字列に限定した一般化Suffix Automatonの構築を検討せよ。
- 次回予告: 次回のテーマは今後のセッションで選定