<分区>
这道题取自往年的acm竞赛。 问题:
- 给定字符串
p长度k <= 1000 - 这个字符串重复无限次，现在我们先取
n < 10^9人物。让我们调用结果字符串s.
任务是找到字符串 s 的唯一子串的计数.
计算不同子串的传统方法是后缀 + lcp 数组，但我们需要 O(n) 来构造它们(使用最快且相当复杂的构造算法)。并且在构造完这些数组之后我们还需要做很多进一步的处理，所以我认为这个解决方案不符合时间要求。
我看过问题分析，但我完全不明白。当然它工作得很好，但他们是如何做到的呢？ 在这里:
如果
p = tt...t对于一些字符串t, 替换p与t.现在让我们假设 p 是非周期性的。f(n)—s前缀中唯一子串的计数长度n.我们假设
n > 2k.然后f(n) = f(n-1)+k. <- 为什么？这背后的逻辑是什么？
证明:
- 让
t是s的后缀. 如果
|t| <= n - k, 然后l也包含在左侧 k 个符号上的 s 中。- 如果
|t| > n - k, 然后l仅作为后缀包含在 s 中。
- 如果
n<=2k无论如何都能解决问题。
非常感谢对此问题分析或您自己的解决方案的任何解释!我不明白我怎么能想出这个函数 f()。这几天一直在思考这个问题。