详细揭秘 NOIP2020字符串匹配 如何不用 Z 函数做到线性

· · 算法·理论

省流：O(\sum\limits_{i=1}^{n} \log(\frac{n}{i}))=O(n)。

没看过原题也没关系，简单来说，你需要对 S 每个前缀 P，求出最大的 k 使得 P^k 也是 S 的前缀。

枚举 P,k，然后用 border 相关周期理论或者哈希 O(1) 判断 P^{k} 是否是 S 的前缀，复杂度是 O(n\ln n) 的。

考虑二分，对每个前缀 P，若 k 满足条件且 k>1，则必有 k-1 满足条件，二分最大的 k，对一个 P 复杂度是 O(\log \frac{n}{|P|})，总复杂度 O(\sum\limits_{i=1}^{n} \log(\frac{n}{i}))。

接下来证明 O(\sum\limits_{i=1}^{n} \log(\frac{n}{i}))=O(n)。

\sum_{i=1}^{n} \log_2(\frac{n}{i}) \\ =\sum_{i=1}^{n}\sum_{k=1}^{\lfloor\log_2 n\rfloor} [\log_2(\frac{n}{i})\geq k] \\ =\sum_{i=1}^{n}\sum_{k=1}^{\lfloor\log_2 n\rfloor}[\frac{n}{i}\geq 2^k] \\ =\sum_{k=1}^{\lfloor\log_2 n\rfloor}\sum_{i=1}^{n}[\frac{n}{i}\geq 2^k] \\ =\sum_{k=1}^{\lfloor\log_2 n\rfloor} O(\frac{n}{2^k}) \\ =O(n)