ACM 问题：长字符串的不同子串数
ACM problem: Number of distinct substrings of long string
这道题取自往年的acm竞赛。
问题：
- 给定字符串
p，长度为 k <= 1000
- 这个字符串重复无限次，现在我们取前
n < 10^9 个字符。让我们调用结果字符串 s.
任务是查找字符串 s.
的唯一子串的计数
计算不同子串的传统方法是后缀 + lcp 数组，但我们需要 O(n) 来构造它们（使用最快且相当复杂的构造算法）。而且在构造完这些数组之后我们还需要做很多进一步的处理，所以我认为这个方案不能满足时间要求。
我看过问题分析，但完全不懂。当然它工作得很好，但他们是如何做到的呢？
这是：
如果 p = tt...t 对于某些字符串 t，请将 p 替换为 t。现在让我们假设 p 是非周期性的。
f(n) — 长度为 n.
s 前缀中唯一子串的计数
让我们假设 n > 2k。然后f(n) = f(n-1)+k。 <- 为什么？这背后的逻辑是什么？
证明：
- 让
t成为s的后缀。
如果|t| <= n - k，则l也包含在左边k个符号的s中。
- 如果
|t| > n - k，则 l 仅作为后缀包含在 s 中。
对于n<=2k问题无论如何都可以解决
非常感谢任何对此问题分析的解释或您自己的解决方案！我不明白我怎么能想出这个函数 f()。这几天一直在想这个问题
我收集到 k 是非周期性输入字符串的长度 p。对于给定的长度l，至多有k个长度为l的不同子串，因为每两个起始位置为全等模k的子串是相同的。 p 是非周期性的关键结果是它的 k 旋转都是不同的，这意味着给定一个长度至少为 k 的子串，我们可以使用它的长度-k前缀，旋转p，确定子串的起始位置取模k。因此，对于 [k, n-k+1] 中的所有 l，我们知道恰好有 k 个长度为 l 的不同子串。对于 [n+1-k, n] 中的所有 l，正好有 n+1-l 个子字符串。对于[0, k)中的所有l，我们用通常的技术来统计。
这道题取自往年的acm竞赛。 问题：
- 给定字符串
p，长度为k <= 1000 - 这个字符串重复无限次，现在我们取前
n < 10^9个字符。让我们调用结果字符串s.
任务是查找字符串 s.
计算不同子串的传统方法是后缀 + lcp 数组，但我们需要 O(n) 来构造它们（使用最快且相当复杂的构造算法）。而且在构造完这些数组之后我们还需要做很多进一步的处理，所以我认为这个方案不能满足时间要求。
我看过问题分析，但完全不懂。当然它工作得很好，但他们是如何做到的呢？ 这是：
如果
p = tt...t对于某些字符串t，请将p替换为t。现在让我们假设 p 是非周期性的。f(n)— 长度为n. 的 让我们假设
n > 2k。然后f(n) = f(n-1)+k。 <- 为什么？这背后的逻辑是什么？
s 前缀中唯一子串的计数
证明：
- 让
t成为s的后缀。 如果
|t| <= n - k，则l也包含在左边k个符号的s中。- 如果
|t| > n - k，则l仅作为后缀包含在 s 中。
- 如果
对于
n<=2k问题无论如何都可以解决
非常感谢任何对此问题分析的解释或您自己的解决方案！我不明白我怎么能想出这个函数 f()。这几天一直在想这个问题
我收集到 k 是非周期性输入字符串的长度 p。对于给定的长度l，至多有k个长度为l的不同子串，因为每两个起始位置为全等模k的子串是相同的。 p 是非周期性的关键结果是它的 k 旋转都是不同的，这意味着给定一个长度至少为 k 的子串，我们可以使用它的长度-k前缀，旋转p，确定子串的起始位置取模k。因此，对于 [k, n-k+1] 中的所有 l，我们知道恰好有 k 个长度为 l 的不同子串。对于 [n+1-k, n] 中的所有 l，正好有 n+1-l 个子字符串。对于[0, k)中的所有l，我们用通常的技术来统计。