[POI 2006] OKR-Periods of Words

题意

对字符串的每个前缀求最长 period 的长度，并把这些长度求和。

思路

长度为 length 的前缀若有 border b，对应 period 长度就是 length-b。要让 period 最长，就要找最短的非空 border。

KMP 的 prefix[length] 给出最长 border，而所有更短 border 都沿 prefix 链出现。令 shortest_border[length] 表示链尾的最短非零长度，则：

text

1shortest_border[length] = shortest_border[j] or j

其中 j = prefix[length]。每个位置只做常数次递推。

Python 知识

x or fallback 会在 x == 0 时取后者，正好表达“已有最短 border，否则当前 border”。
使用 1-based 长度数组能让 prefix[j] 与数学定义直接对应。
两个 array("i") 在百万长度下仍只占约 8 MB。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22import sys
from array import array


n, word = sys.stdin.buffer.read().split()
n = int(n)
prefix = array("i", [0]) * (n + 1)
shortest_border = array("i", [0]) * (n + 1)
answer = 0

for length in range(2, n + 1):
    j = prefix[length - 1]
    while j and word[length - 1] != word[j]:
        j = prefix[j]
    if word[length - 1] == word[j]:
        j += 1
    prefix[length] = j
    if j:
        shortest_border[length] = shortest_border[j] or j
        answer += length - shortest_border[length]

print(answer)

复杂度

时间 $O(n)$ ，空间 $O(n)$ 。

总结

前缀函数只直接给最长 border，但它的链包含全部 border；在链上递推所需统计量是常见技巧。

[POI 2006] OKR-Periods of Words

目录

题意

思路

Python 知识

代码

复杂度

总结