CF526D Om Nom and Necklace

有一天，Om Nom 发现了一串有 $n$ 颗颜色各异的珠子。他决定从这串珠子中剪下前面若干颗珠子，做成一串珠子项链送给他的女朋友 Om Nelly。 Om Nom 知道，他的女朋友喜欢美丽的图案。因此，他希望项链上的珠子能够形成一种规律的模式。一个珠子序列 $S$ 被称为规律序列，如果它可以表示为 $S = A + B + A + B + A + \dots + A + B + A$，其中 $A$ 和 $B$ 是某些珠子序列（$+$ 表示拼接序列），这个序列总共有恰好 $2k+1$ 个部分，其中 $A$ 出现 $k+1$ 次，$B$ 出现 $k$ 次，交替排列。Om Nelly 知道她的朋友是一位狂热的数学家，所以即使 $A$ 或 $B$ 是空序列，她也不介意。 请帮 Om Nom 计算，他在剪下前面若干颗珠子（至少一颗，最多全部）时，在多少种情况下能够得到一个规律的珠子序列。剪下来的珠子的顺序不会改变。

第一行包含两个整数 $n$ 和 $k$（$1\leq n,k\leq 1000000$），分别表示 Om Nom 发现的珠子数目和上述规律序列定义中的 $k$。 第二行是一个长为 $n$ 的小写拉丁字母序列，表示珠子的颜色。每种颜色对应一个字母。

输出一个由 $n$ 个 $0$ 或 $1$ 组成的字符串。如果前 $i$ 颗珠子的序列是规律序列，则第 $i$ 位为 $1$，否则为 $0$，其中 $1 \leq i \leq n$。

在第一个样例中，前 6 颗珠子的序列是规律序列（可以取 $A=$""，$B=$"bca"），前 7 颗珠子的序列也是规律序列（可以取 $A=$"b"，$B=$"ca"）。 在第二个样例中，例如前 13 颗珠子的序列是规律的，如果取 $A=$"aba"，$B=$"ba"。 由 ChatGPT 5 翻译