CF526D Om Nom and Necklace 题解

· · 题解

前言

题目链接

虽然题解区中已经有了 KMP 的解法，但个人认为大部分已有的 KMP 题解说的都不太明白，有的甚至还不太严谨，因此写了篇自认为明白一点的。

正文

常识级别的结论：长度为 n 的字符串其最小循环节长度为 n-nxt_n，若 n\bmod{(n-nxt_n)} 不为 0 则不存在循环节。

考虑将 AB 作为一个整体看待，形如 ABABA 的字符串一定也可以表示成 SSSST 的形式，如果令 B 为空的话还可以直接表示成 SSSSS 的形式，其中 T 是 S 的一个前缀。

记 d=n/(n-nxt_n)，因为一共出现了 k 次 AB，所以每一个 AB 都出现了 d/k 次 S，而 A 就是去掉 k 次 AB 后剩下的 d\bmod k 那一部分，因此 B 中就出现了 d/k-d\bmod k 个 S。

如果说原串存在循环节，此时 B 是可以为空的，因此只需要 d/k-d\bmod k\ge0 即可；否则 B 是不可以为空的，需要满足 d/k-d\bmod k>0。

代码

#include<bits/stdc++.h>
//#define int long long
#define fi first
#define se second
#define Mp make_pair
#define pb emplace_back
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rof(i,a,b) for(int i=a;i>=b;i--)
#define clr(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
const int N=4e6+5;
const int mod=1e9+7;
const int inf=1e9;
int n,k,ans[N],nxt[N];
char s[N];
void Main(){
    scanf("%d%d",&n,&k);
    scanf("%s",s+1);
    for(int i=2,j=0;i<=n;i++){
        while(j&&s[i]!=s[j+1]) j=nxt[j];
        if(s[i]==s[j+1]) j++;
        nxt[i]=j;
    }
    For(i,1,n){
        int len=i-nxt[i],d=i/len;
        if(i%len) ans[i]=(d/k-d%k)>0;
        else ans[i]=(d/k-d%k)>=0;
    }
    For(i,1,n) printf("%d",ans[i]);
}
signed main(){
    int T=1;
    while(T--) Main();
    return 0;
}