原题
KMP
方法一：
听说是ex-kmp——来自学姐
ex-kmp是处理两个串s和t之间，t的每一个后缀在s中的最长前缀的长度的一个算法。
它很像manacher（至少我和学姐这么认为），记录了一个maxright，对于当前t中的位置i，如果他小于等于maxright，那么他的答案等于产生当前maxright的该位的答案，如下图。
然后如果当前位加上当前答案是大于maxright的，那么把答案减小maxright后进行暴力匹配。
如果他是大于maxright的，那么我们就暴力匹配，eg。
每一位处理后进行maxright的更新。附代码如下（写的不好看，但是自认为逻辑清晰易懂）
for (int i=2;i<=n;i++)
{
if (maxr>=i)
{
a[i]=a[i-from+1];
if (a[i]+i>maxr)
{
a[i]=maxr-i+1;
while (i+a[i]<=n)
if (s[a[i]+1]==s[i+a[i]]) a[i]++;
else break;
}
}
else
{
while (i+a[i]<=n)
if (s[a[i]+1]==s[i+a[i]]) a[i]++;
else break;
}
if (i+a[i]-1>maxr) maxr=i+a[i]-1,from=i;
}
//这个代码是对s和s本身进行了处理……
然后我们只要枚举循环节的长度，然后可行的位置就是枚举完成的后一位的a值所覆盖的部分
//真××难想！
#include<cstdio>
#include<algorithm>
#define N 1000010
using namespace std;
int n,k,a[N],from,maxr,q[N],sum[N];
char s[N];
int main()
{
scanf("%d%d",&n,&k);
scanf("%s",s+1);
a[1]=n;
for (int i=2;i<=n;i++)
{
if (maxr>=i)
{
a[i]=a[i-from+1];
if (a[i]+i>maxr)
{
a[i]=maxr-i+1;
while (i+a[i]<=n)
if (s[a[i]+1]==s[i+a[i]]) a[i]++;
else break;
}
}
else
{
while (i+a[i]<=n)
if (s[a[i]+1]==s[i+a[i]]) a[i]++;
else break;
}
if (i+a[i]-1>maxr) maxr=i+a[i]-1,from=i;
}
for (int i=1;i*k<=n;i++)
{
bool is=0;
for (int j=1;j<k;j++)
{
if (a[j*i+1]<i)
{
is=1;
break;
}
}
if (!is) q[i*k]++,q[min(i*k+a[i*k+1],i*(k+1))+1]--;
}
for (int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+q[i];
if (sum[i]>0) putchar('1');else putchar('0');
}
return 0;
}
方法二：
简单的kmp——来自子恒
首先，对于这道题，我们会得出一个答案：
如果一个字符串是n个长度为k循环节，那么next[n]=n-k（显然）
所以对于这道题也是一样的。
对于一个合法的字符串，他只有两种存在方式：
SSSSSSS
和SSSSSST
（A包含了x个S（也就是T），而B包含了y个S（也就是S-T））
如果是第一种情况，那么S重复的次数num是n/(n-next[n])（前提是整除），那么AB就是num/k，A就是num%k。判断条件位num/k>=num%k（因为A属于AB）
如果是第二种情况，那么A=T，B=SSSSS-T，AB的个数仍是num/k，A仍是num%k，因为T!=S，所以判定条件是num/k>num%k
O(n)即可！
//附上子恒大佬的代码
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e6+5;
char s[N];
int nxt[N];
char ans[N];
void getnext(int m){
int j=0;
for(int i=2;i<=m;i++){
while(j!=0&&s[j+1]!=s[i])j=nxt[j];
if(s[j+1]==s[i])j++;
nxt[i]=j;
}
return;
}
int main(){
int m,k;
scanf("%d%d%s",&m,&k,s+1);
memset(ans,'0',sizeof(ans));
getnext(m);
for(int n=1;n<=m;n++){
int num=n/(n-nxt[n]);
if(n%(n-nxt[n])==0){
if(num/k>=num%k){
ans[n-1]='1';
}
}else{
if(num/k>num%k){
ans[n-1]='1';
continue;
}
}
}
ans[m]=0;
puts(ans);
return 0;
}
另外：这题卡输出，请用putchar！
鸣谢各位orz的耐心讲解！