自动搬运

查看原文

来自洛谷，原作者为

	5k_sync_closer 数据结构真可爱。

搬运于2025-08-24 22:07:15，当前版本为作者最后更新于2025-01-09 11:38:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

没卡常，目前用时是次优解的一半左右。

推销 Lyndon 理论学习笔记（没写完）

P5108 仰望半月的夜空

给一个字符串 $s$，对 $i\in[1,|s|]$ 问长度为 $i$ 的最小子串的第一次出现。

先给复杂度：问最后一次出现可以 $O(|s|)$，问第一次出现可以结合哈希二分做到 $O(|s|\log|s|)$。

字典序问题，可以在 Lyndon 分解上考虑，设分解得到 $s=w_1+\dots+w_k$。

考虑长度为 $i$ 的最小子串在哪里起头。首先根据 Lyndon 串的定义，在某个 $w_p$ 中间起头肯定不优，

而且分解出的 Lyndon 串字典序是单调不增的，所以应该在尽量靠后的 $w_p$ 起头，

所以可以得出结论：应该在 $|w_p+w_{p+1}+\dots+w_k|\ge i$ 的最后一个 $w_p$ 处起头，

但这个子串不一定只在这里出现，考虑它还在哪里出现过。

分解出的 Lyndon 串字典序是单调不增的，所以这个子串只在 $w_p$ 及其前的若干个 Lyndon 串中出现。

二分这个子串最早在哪里出现即可。

#include <cstdio>
#include <cstring>
char _[300050];
int n, o, S, l[300050], a[300050];
unsigned long long p[300050], h[300050];
int Q(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; }
int main()
{
    scanf("%d%d", &S, &n);
    if (S == 26)
    {
        scanf("%s", _ + 1);
        for (int i = 1; i <= n; ++i)
            a[i] = _[i];
    }
    else
    {
        for (int i = 1; i <= n; ++i)
            scanf("%d", a + i);
    }
    for (int i = p[0] = 1; i <= n; ++i)
        p[i] = p[i - 1] * 10000019, h[i] = h[i - 1] * 10000019 + a[i];
    int i = 1, j, k;
    while (i <= n)
    {
        j = i + 1, k = i;
        while (j <= n)
        {
            if (a[j] == a[k])
                ++j, ++k;
            else if (a[j] > a[k])
                ++j, k = i;
            else
                break;
        }
        while (i <= k)
            l[++o] = i, i += j - k;
    }
    for (int i = 1, j = o; i <= n; ++i)
    {
        if (n - l[j] + 1 < i)
            --j;
        int L = 1, R = j;
        while (L <= R)
        {
            int M = L + R >> 1;
            if (Q(l[M], l[M] + i - 1) == Q(l[j], l[j] + i - 1))
                R = M - 1;
            else
                L = M + 1;
        }
        printf("%d ", l[L]);
    }
    return 0;
}