玄学的字符串算法可能并不能讲明白，谅解
kmp算法流程
假如,(A=abababaababacb),(B=ababacb).我们来看看(KMP)是怎么工作的。我们用两个指针(i)和(j)分别表示，(A_{i-j+1 ightarrow i})与(B_{1 ightarrow j})完全相等。也就是说,(i)是不断增加的，随着(i)的增加(j)相应地变化，且(j)满足以(A_i)结尾的长度为(j)的字符串正好匹配(B)串的前(j)个字符（(j)越大越好），现在需要检验 (A_{i+1})和(B_{j+1})的关系。当(A_{i+1}=B_{j+1})时,(i)和(j)各加一；当(j=m)了，我们就说(B)是(A)的子串（(B)串已经完整匹配了），并且可以根据这时的(i)值算出匹配的位置。当 (A_{i+1} eq B_{j+1}) ,(KMP)的策略调整(j)的位置（减小(j)值）使得(A_{i-j+1 ightarrow i})与(B_{1 ightarrow j})保持匹配且尝试匹配新的(A_{i+1})与(B_{1 ightarrow j})（(j)的值这里仍然尽量大）。
举例说明
当(i=j=5)时
此时，(A_6 eq B_6)。表明，此时(j)不能等于(5)了，我们要把(j)改成比它小的值(j') ,(j')可能是多少呢？仔细想一下，我们发现，(j')必须要使得(B_{1 ightarrow j})中的头(j')个字母和末(j')个字母完全相等（这样就可以直接把(B)串移到后面来）。这个(j')当然要越大越好,在这里，(B_{1 ightarrow 5}=ababa)头(3)个字母和末(3) 个字母都是(aba),而当新的(j)为(3)时(A_6)恰好和(B_4)相等,于是，(i)变成了(6),而(j)则变成了(4)
结论：
循环节问题：最短循环节的长度(len=i-fail_i)，如果(i%len=0)，那么就存在循环节，否则不存在
例题：
这道题我们想要求出前缀是否满足(ABABABA)的形式，即(A)和(B)交替出现且最后(A)结尾，又因为(A)可以为空串，就可以改写成(SSSSSA)和(SSSSS)两种形式，其中(S)为一个完整的循环节，(A)为循环节加一个前缀。
不难发现几个循环节可以拼成一个循环节，所以给出的形式中(AB)就相当于若干最短循环节(frac{num}{k})个循环节拼在一起,算数意义也就是(num)个循环节平均分出(k)个，那么剩余的(A)就相当于若干循环节加若干循环节的前缀(num\%k)个循环节+(W)，算数意义就是(num)个循环节平均分成(k)后剩下的循环节个数
由于我的(A)是(AB)的一部分,所以第一种情况我(A)包含的循环节个数要小于(AB)包含的循环节个数，因为我(A)还会加上一个循环节的前缀，如果个数相等(A)就比(AB)长了，显然矛盾，更别提个数比(AB)大，第二种情况只需要(A)包含的循环节个数等于(AB)包含的循环节个数就可以,因为(A)此时可以为空
所以我们可以得到判断公式:
(egin{cases}ans_i = (frac{num}{k}-num\%k > 0)&i\%len eq 0 \ ans_i = (frac{num}{k}-num\%kgeq 0)&i\%len=0 end{cases})
code：
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = 1e6+10;
int n,k;
char s[maxn];
int ans[maxn],kmp[maxn];
int main(){
scanf ("%d%d",&n,&k);
scanf ("%s",s+1);
int j = 0;
for (int i = 2;i <= n;i++){
while (j&&s[i] != s[j+1]) j = kmp[j];
if (s[i] == s[j+1]) j++;
kmp[i] = j;
}
for (int i = 1;i <= n;i++){
int num = i-kmp[i];int len = i/num;
if (i%num != 0) ans[i] = ((len/k-len%k)>0);
else ans[i] = ((len/k-len%k)>=0);
}
for (int i = 1;i <= n;i++) printf("%d",ans[i]);
return 0;
}