题目描述：
有一天，欧姆诺姆发现了一串长度为n的宝石串，上面有五颜六色的宝石。他决定摘取前面若干个宝石来做成一个漂亮的项链。
他对漂亮的项链是这样定义的，现在有一条项链S，当S=A+B+A+B+A+...+A+B+A的时候是漂亮的，这儿A，B是一些宝石串，“+”表示连接操作。S中有k+1个A和k个B组成。A和B可能是空串。
现在给出宝石串，问怎么切前几个才能得到一个漂亮的宝石项链。他切下来之后不会改变宝石的顺序。
样例解释：
在这个样例中前6个可以组成漂亮的串（ A="", B="bca"）。前7个也可以（A="b", B="ca"）。
题解：
首先用kmp算法可以将字符串的一个前缀划分成SSSS....ST的形式。
下面考虑如果T=S，R为有多少个S，那么每个AB的要求就是要有R/k个S，最后会余下来R%k个S，那么把余下来的这部分当作A，其余部分当作B即可，这里B可以为空串
所以条件就是R/k-R%k>0
如果T!=S，每个AB的要求仍然是有R/k个S，最后会余下来R%k个S加上T，这时就需要把余下的部分当成A，剩下的部分当成B，但是这里B不能为空串，不然就不能凑出来AB（因为A不是S..SS，是S..ST)了
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 2e6;
int n, k;
char s[maxn];
int ans[maxn], fail[maxn];
int main()
{
cin>>n>>k;
cin>>s;
int j = ;
fail[] = ;
ans[] = ;
if(k == ) ans[] = ;
for(int i = ; i < n; i++){
j = fail[i];
while(j && s[i] != s[j]) j = fail[j];
j = s[i] == s[j] ? j+ : ;
fail[i+] = j; int Q = i-j+, R = (i+)/Q;
if((i+)%Q == ) ans[i] = R/k >= R%k;
else ans[i] = R/k > R%k;
}
for(int i = ; i < n; i++) putchar(ans[i] ? '' : '');
return ;
}