KMP的特殊性质之CF526D

· · 题解

题目传送门

这道题就纯属水紫好吧，顶多是个绿……

话不多说，进入正题。

这道题我们可以利用 KMP 的性质来做，我们直接上推算过程：

首先我们可以把 AB 分为名为 C 的一组，那么字符串可以变成 CC……CA，其中 C 有 k 个，且 A 是 C 的前缀（由定义而知）。

接着，我们进行求 next 数组来扫一遍。首先，在第一个 C 内，所指向的 next 都是最开始的地方。第一个 C 结束的地方为临界点。

开始扫后面的值，当扫到第二个 C 的时候，所指向的 next 刚好是第一个 C 里的相同位置。第二个 C 扫描结束后，所指向的 next 刚好扫完第一个 C。

以此类推，后面每次扫到的都是上一个 C 内的相同位置。扫到最后一个点，也就是最后的 A 结束时，它指向了最后一个 C 内的同一位置。

我们可以通过最后一个点和它的 next 指向的地方相减得到 C 的长度，再通过总长和 C 的长度确定 C 的个数和 A 的长度，只要段数是 k 且 A 的长度在 C 以内就可以了。

但是！

我们举个例子：

9 2
ababababa

我们的段数是大于 k 的，本来是有解，我们的程序把它判定为无解了。怎么办呢？

我们可以先把它原本多少段先求出来，然后看看究竟是 C 的数量除以 k 大，还是膜 k 大，就可以判断了（对应“只要段数是 k 且 A 的长度在 C 以内就可以了”）。

有些坑点和详细细节写代码里的：

#include<bits/stdc++.h>
using namespace std;
int n,m,p,h,i=0,j=-1,nxt[1000010]={-1};
char c[1000010];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>c[i];
    while(i<n){ //求next不用说了
        if(j==-1||c[i+1]==c[j+1]){
            i++,j++;
            nxt[i]=j;
        }else j=nxt[j];
    }
    for(int i=1;i<=n;i++){
        p=i-nxt[i]; //C的长度
        h=i/p; //C的个数
        if(i%p)cout<<((h/m-h%m)>0); //如果不为空，大于就行了
        else cout<<((h/m-h%m)>=0); //当A为空的时候，个数除以k（代码里是m）是要大于等于才行的
    }
    return 0;
}

更正信息