【Henu ACM Round#16 F】Om Nom and Necklace

在这里输入题意

【题解】

KMP算法可以把"i前缀"pre[i] 分成ssssst的形式这里t是s的前缀。

然后s其实就是pre[i]中的前 i+1-f[i]个字符组成的
字符串。
特殊的,t可能就是一个空串。
比如abcdefg
这里f是kmp算法中的f数组

然后t有两种可能
① t==s
　这样的话,整个前缀就是
　sssssss..ss了
　这里有(i)/(i-f[i])个s
　设为num;
　我们可以用这些s来构造ababababa的形式。
　则我们需要k个ab 然后一个a
　我们可以用num/k个s来构成ab,然后num%k个s来
　构成一个a

　我们只需要判断一下num/k是否大于等于num%k就
　好了,因为ab是由num/k个s构成的,a是由num%k个s
　构成的,ab的长度肯定要大于等于a的长度的
　(a可以为空串,所以等于也可以)
　(因此num/k-num%k个s就是b了)

　用num/k个s来构成ab,可以让ab的长度尽量长一点
　然后a的长度也变成尽可能地短了。
　->只有num%k
　这就让答案尽可能地正确了。
　贪心吧。
②t!=s
　这种情况其实也类似。
　这不过那个t只能算成是a中的了。
　因此num/k不能等于num%k了。
　只能num/k>num%k
　然后那个t加在num%k个s后面组成a
　这样a的长度才不会超过num/k.

我写的KMP中f[i]指的是如果i失配了下一个和谁尝试匹配,也就是说s[0..f[i]-1]=s[i-1-f[i]+1..i-1] 因此n-1的循环节要i循环到n才能知道。

【代码】

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e6;

char s[N+10];
int f[N+10],n,k;

int main(){
	#ifdef LOCAL_DEFINE
	    freopen("rush_in.txt", "r", stdin);
	#endif
	ios::sync_with_stdio(0),cin.tie(0);
    cin >> n >> k;
    cin >>s;
    f[0] = f[1] = 0;
    for (int i = 1;i <n;i++){
        int j = f[i];
        while (j>0 && s[i]!=s[j]){
            j = f[j];
        }
        f[i+1]=(s[i]==s[j]?(j+1):0);
    }
    for (int i = 1;i <= n;i++){
        //f[i] = x
        int num = i/(i-f[i]);
        int ab = num/k,a = num%k;
        if (i%(i-f[i])==0){
            if (ab>=a){
                cout<<1;
            }else {
                cout<<0;
            }
        }else{
            if (ab>a){
                cout<<1;
            }else{
                cout<<0;
            }
        }
    }
	return 0;
}