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