CF526D Om Nom and Necklace 题解

题目链接：CF526D Om Nom and Necklace

题意：

已知长度为 $n$ 的字符串 $s$，对于 $s$ 的每一个前缀子串（即对于每一个 $i$，$s$ 中从第 $1$ 个字符到第 $i$ 个的所有字符组成的字符串，$1\leq i\leq n$），如果满足 $\texttt{ABABA…BA}$ 的形式（$A$、$B$ 可以为空，也可以是一个字符串，$A$ 有 $k+1$ 个，$B$ 有 $k$ 个），则请输出 $1$；否则输出 $0$，注意：$n$ 和 $k$ 给定。

输入格式：

The first line contains two integers $n$, $k$ ($1\leq n,k\leq 10^6$) — the number of beads on the thread that Om Nom found and number $k$ from the definition of the regular sequence above.

The second line contains the sequence of $n$ lowercase Latin letters that represent the colors of the beads. Each color corresponds to a single letter.

输出格式：

Print a string consisting of $n$ zeroes and ones. Position $i$ ($1\leq i\leq n$) must contain either number one if the first $i$ beads on the thread form a regular sequence, or a zero otherwise.

稍微试一试就会发现，如果一个前缀的最长 Border 是可重叠的，那非重叠部分就是 $\mathtt{A}$ 的最小形式

当然这没有考虑到 $k$ 的问题，不过我们可以发现，去掉最右侧的 $\mathtt{A}$ ，左侧就是若干个 $\mathtt{AB}$ 。

这有什么用呢？我们令 $\mathtt{C} = \mathtt{AB}$ ，则 $\mathtt{A}$ 为 $\mathtt{C}$ 的一个前缀。

并且容易发现，记当前位置为 $i$ ，则 $\operatorname{fail} i$ 一定指向了上一个这样的 $i$ ，也就是上一个 $\mathtt{C}$ 的末尾。

这下就好办了，我们能够得知 $\mathtt{C}$ 的长度，就能计算出 $\mathtt{C}$ 的个数和 $\mathtt{A}$ 的长度，同时也能算出 $\mathtt{B}$ 的长度。

不过，有可能会出现 $\mathtt{A}$ 为空的情况，这个只需要分类讨论一下就好，其实就是个等号的差异（

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e6 + 15))

int n,m,fail[N]; char s[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m >> (s + 1);
    for(int i = 2, j = 0; i <= n; i++)
    {
        while(j && s[i] != s[j + 1]) j = fail[j];
        if(s[i] == s[j + 1]) ++j; fail[i] = j;
    }
    for(int i = 1,p,h; i <= n; i++)
    {
        p = i - fail[i], h = i / p;
        if(i % p) cout << ((h / m - h % m) > 0);
        else cout << ((h / m - h % m) >= 0);
    }
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/312795/solution-cf526d