Codeforces ZeptoLab Code Rush 2015 D.Om Nom and Necklace(kmp)

题目描述：

有一天，欧姆诺姆发现了一串长度为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 = 0;
    fail[0] = 0;
    ans[0] = 0;
    if(k == 1) ans[0] = 1;
    for(int i = 1; i < n; i++){
        j = fail[i];
        while(j && s[i] != s[j]) j = fail[j];
        j = s[i] == s[j] ? j+1 : 0;
        fail[i+1] = j;

        int Q = i-j+1, R = (i+1)/Q;
        if((i+1)%Q == 0) ans[i] = R/k >= R%k;
        else ans[i] = R/k > R%k;
    }
    for(int i = 0; i < n; i++) putchar(ans[i] ? '1' : '0');
    return 0;
}