691. Long substring with many repetitions

Given a character string $s$, we define $L(k,s)$ to be the length of the longest substring of $s$ which appears at least $k$ times in $s$, or $0$ if such a substring does not exist. For example, $L(3,\text{“bbabcabcabcacba”})=4$ because of the three occurrences of the substring $\text{“abca”}$, and $L(2,\text{“bbabcabcabcacba”})=7$ because of the repeated substring $\text{“abcabca”}$. Note that the occurrences can overlap.

Let $a_n$, $b_n$ and $c_n$ be the $0/1$ sequences defined by:

• $a_0 = 0$
• $a_{2n} = a_{n}$
• $a_{2n+1} = 1-a_{n}$
• $b_n = \lfloor\frac{n+1}{\varphi}\rfloor - \lfloor\frac{n}{\varphi}\rfloor$ (where $\varphi$ is the golden ratio)
• $c_n = a_n + b_n - 2a_nb_n$

and $S_n$ the character string $c_0\ldots c_{n-1}$. You are given that $L(2,S_{10})=5$, $L(3,S_{10})=2$, $L(2,S_{100})=14$, $L(4,S_{100})=6$, $L(2,S_{1000})=86$, $L(3,S_{1000}) = 45$, $L(5,S_{1000}) = 31$, and that the sum of non-zero $L(k,S_{1000})$ for $k\ge 1$ is $2460$.

Find the sum of non-zero $L(k,S_{5000000})$ for $k\ge 1$.

691. 重复多次的长子串

给定一个字符串 $s$，记 $L(k,s)$ 为：所有在 $s$ 中至少重复出现 $k$ 次的子串中，长度的最大值；若不存在符合要求的子串，函数值为 $0$。例如有 $L(3,\text{“bbabcabcabcacba”})=4$，因为子串 $\text{“abca”}$ 出现了 3 次；$L(2,\text{“bbabcabcabcacba”})=7$，因为 $\text{“abcabca”}$ 出现了 7 次。请注意，出现的子串之间允许有公共部分。

记 $\{a_n\}$、$\{b_n\}$ 和 $\{c_n\}$ 为三个 $0/1$ 序列，其定义如下：

• $a_0 = 0$
• $a_{2n} = a_{n}$
• $a_{2n+1} = 1-a_{n}$
• $b_n = \lfloor\frac{n+1}{\varphi}\rfloor - \lfloor\frac{n}{\varphi}\rfloor$（$\varphi$ 是黄金分割比 $\frac{1 + \sqrt{5}}{2}$）
• $c_n = a_n + b_n - 2a_nb_n$

并记 $S_n$ 为 $c_0\ldots c_{n-1}$ 顺序组成的 $0/1$ 字符串。已知：$L(2,S_{10})=5$、$L(3,S_{10})=2$、$L(2,S_{100})=14$、$L(4,S_{100})=6$、$L(2,S_{1000})=86$、$L(3,S_{1000}) = 45$、$L(5,S_{1000}) = 31$；且 $k\ge 1$ 时，所有非零的 $L(k,S_{1000})$ 之和为 $2460$。

求 $k\ge 1$ 时，所有非零的 $L(k,S_{5000000})$ 之和。

点 这个链接 回到源站。

点 这个链接 回到详细版题目目录。