Codeforces

Luogu

定义

$$f(S)=\left[\exists A,\exists B,S=\underbrace{A+B+A+\cdots+A+B+A}_{k+1\text{个}A,k\text{个}B}\right]$$

$\forall i\in[1,|S|]$，求 $f(pre(i))$ 的值。

分析

我们把条件转化一下，变成
$$
f(S)=\left[\exists A,\exists B\text{为}A\text{的前缀},S=\underbrace{A+A+\cdots+A+A+B}_{k\text{个}A}\right]
$$
定义
$$
g(S)=\left[\exists A,S=\underbrace{A+A+\cdots+A+A}_{k\text{个}A}\right]
$$
我们可以先找到所有 $g(pre(i))=1$ 的 $i$，再往后扩展。

枚举 $i=|A|$，那么 $g(pre(ik))=1$ 的充要条件是 $S[1..ik-i]=S[i+1..ik]$。

因此我们可以将 $suf(i+1)$ 和 $S$ 匹配，如果匹配长度 $\geq i(k-1)$ 说明合法。

这个匹配的实质是后缀与前缀匹配，因此可以使用 Z-Algorithm，匹配长度即 $z(i+1)$。

现在考虑往后扩展。能扩展到 $j$ 的条件是 $S[ik+1..j]$ 是 $A$ 的前缀，即是 $S$ 的一个长度 $\leq i$ 的前缀。因此扩展长度就是 $\min\left\{i,z(ik+1)\right\}$。

这时我们需要把 $[ik,ik+\min\left\{i,z(ik+1)\right\}]$ 内的答案设为 $1$，差分即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000000+10;

int n,k; char s[N]; int z[N],d[N];

int main() {
    n=read(),k=read(); scanf("%s",s+1);
    for (int i=2,mr=1,mid;i<=n;++i) {
        z[i]=i<mr?min(z[i-mid+1],mr-i):0;
        while (s[1+z[i]]==s[i+z[i]]) ++z[i];
        if (i+z[i]>mr) mr=i+z[i],mid=i;
    }
    z[1]=n;
    for (re int i=1;i*k<=n;++i)
        if (z[1+i]>=i*(k-1))
            ++d[i*k],--d[i*k+min(z[i*k+1],i)+1];
    for (re int i=1;i<=n;++i) d[i]+=d[i-1];
    for (re int i=1;i<=n;++i) putchar(d[i]?'1':'0');
    return 0;
}