1

这个问题取自去年的 acm 比赛。问题：

  • p给定长度的字符串k <= 1000
  • 这个字符串被无限重复，现在我们取第一个n < 10^9字符。让我们调用结果字符串s。

任务是查找字符串的唯一子串的计数s。

计算不同子串的传统方法是 suffix + lcp 数组，但我们需要 O(n) 来构造它们（使用最快且非常复杂的构造算法）。而在构建完这些数组之后，我们还需要做很多进一步的处理，所以我认为这个解决方案不能满足时间要求。

我已经阅读了问题分析，但我根本不明白。当然它工作得很好，但他们是怎么做到的呢？这里是：

  • 如果p = tt...t对于某些字符串t，请替换p为t. 现在让我们假设 p 是非周期性的。

  • f(n)s—长度为前缀的唯一子串计数n。

  • 让我们假设n > 2k. 然后f(n) = f(n-1)+k。<- 为什么？其背后的逻辑是什么？

证明：

  • lett是 的后缀s。

  • 如果|t| <= n - k, thenl也包含在左侧 k 个符号上的 s 中。

    • if |t| > n - k, thenl仅作为后缀包含在 s 中。

  • 因为n<=2k问题无论如何都可以解决。

对此问题分析或您自己的解决方案的任何解释都非常感谢！我不明白我怎么能想出那个函数 f()。这几天一直在想这个问题。

4

1 回答 1

1

我认为这k是非周期性输入字符串的长度p。对于给定的长度l，最多有k长度不同的子串l，因为每两个起始位置为全等模的子串k是相同的。p非周期性的关键结果是它的k旋转都是不同的，这意味着给定长度至少为 的子串k，我们可以使用它的长度k前缀，即 的旋转p，来确定子串模的起始位置k。因此，对于所有l的[k, n-k+1]，我们知道有完全k不同的长度子串l。对于所有l的[n+1-k, n]，有n+1-l子串。对于所有l的[0, k)，我们使用通常的技术来计数。

于 2019-09-18T12:59:40.767 回答