---

Problem 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}{\phi }\rfloor -\lfloor \frac{n}{\phi }\rfloor$ (where $\phi$ is the golden ratio)
• $c_n=a_n+b_n-2a_n{b}_n$

and $S_n$ the character string $c_0\dots 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$.

---

多次重复的长子串

给定字符串$s$，记$L(k,s)$为在$s$中至少重复出现$k$次的子串中最长子串的长度，如果这样的子串不存在则取$0$。例如，$L(3,\text{“bbabcabcabcacba”})=4$，因为子串$\text{“abca”}$重复出现了三次；而$L(2,\text{“bbabcabcabcacba”})=7$因为子串$\text{“abcabca”}$重复出现了两次。注意子串的多次出现之间允许重复使用字符。

记$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}{\phi }\rfloor -\lfloor \frac{n}{\phi }\rfloor$（其中$\phi$表示黄金比$\frac{1+\sqrt{5}}{2}$）
• $c_n=a_n+b_n-2a_n{b}_n$

记$S_n$为字符串$c_0\dots c_{n-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})$之和。

---