zeptolab

链接：https://codeforces.com/contest/526/problem/D
思路：明明点的后缀数组题，为什么要给我来kmp二连啊。。。这个题我们可以分情况讨论一下，如果包含空串，那么那个前缀串就是某个子串的k或者k+1倍，否则的话，就是某个前缀串k倍 + 一部分，前者非常好处理，用循环节就可以处理了，后者我们要考虑一下，其实只要保证k的完整部分比后面长就行了(因为求这个过程中已经保证了是一个循环的)，其实这个题就做完了，算是一个kmp思维好题。

链接：


using namespace std;

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

void (char *P){
    f[0] = f[1] = 0;
    for(int i = 1; i < n; i++){
        int j = f[i];
        while(j && P[i] != P[j]) j = f[j];
        f[i + 1] = P[i] == P[j] ? j + 1 : 0;
    }
}

bool check(int x){
    if(x % (x - f[x]) == 0 && ((x / (x - f[x]) % k == 0) || x / (x - f[x]) % (k + 1) == 0 || x / (x - f[x]) == 2 * k + 1)) return true;
    
    if (x / (x - f[x]) / k > x / (x - f[x]) % k)return true;
    return false;
}

int main(){
    scanf("%d %d %s", &n, &k, s);
    getfail(s);
    for(int i = 1; i <= n; i++){
        if(check(i))putchar('1');
        else putchar('0');
    }
    puts("");
    return 0;
}

近期文章

近期评论

标签

热门

文章归档

分类目录

功能