CF526D Om Nom and Necklace

gate

用时：反正挺久的

给定长度为(n)的字符串和整数(k)，问每个前缀能否拆成(ABABA)（(B)可以为空，即(AAAAA)）（(k+1)个(A)）的形式。
设(AB)为(S)，则(A)为(S)的前缀。
问题转化为拆成(SSSSA)或(SSSSS)
(KMP)，通过(fail)数组可以求出最小循环节长度为(n-f[n])。
字符串中共有(sum = n/(n-f[n]))个最小循环节。
即，(S)的长度为(sum/k)，(A)的长度为(sum\%k)，(B)的长度为(sum/k-sum\%k)
若(n\%(n-f[n]) ot=0)，即字符串不是恰好由(n-f[n])的循环组成的，形式为(SSSSA)，
则必须有(B)的长度(>0)。
否则若(n\%(n-f[n])=0)，即可能为(SSSSS)，
则有(B)的长度(ge0)

注意这里(KMP)的写法。
code

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#define MogeKo qwq
using namespace std;

const int maxn = 1e6+10;
int n,k,f[maxn];
char s[maxn];

void getf() {
	for(int i = 2,j = 0; i <= n; i++) {
		while(j && s[i] != s[j+1]) j = f[j];
		if(s[i] == s[j+1]) j++;
		f[i] = j;
	}
}

int main() {
	scanf("%d%d",&n,&k);
	scanf("%s",s+1);
	getf();
	for(int i = 1; i <= n; i++) {
		int sum = i/(i-f[i]);
		if(i%(i-f[i]) != 0)
			if(sum/k > sum%k) printf("1");
			else printf("0");
		else if(sum/k >= sum%k) printf("1");
			 else printf("0");
	}
	return 0;
}