ACM模版

描述

题解

这个题思路好巧妙啊，我想了好久都没有想通，找了一个前辈的题解才搞懂……看了好大一会儿~~~

贴一下该大牛的题解：

来源：_TCgogogo_’s blog 感谢大神详细的题解！！！

代码

#include <cstdio>
#include <cstring>

int const MAXN = 1e6 + 5;

int n, k;
char s[MAXN];
char ans[MAXN];
int nt[MAXN];

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

int main()
{
    scanf("%d%d%s", &n, &k, s);

    get_nt();

    for(int i = 0; i < n; i++)
    {
        int len = i - nt[i];
        int num = (i + 1) / len;
        int t = num % k;
        if (t == 0)
        {
            ans[i] = '1';
        }
        else
        {
            if (len * num != i + 1)
            {
                t++;
            }
            if (num / k >= t)
            {
                ans[i] = '1';
            }
            else
            {
                ans[i] = '0';
            }
        }
    }
    printf("%s\n", ans);

    return 0;
}