题目描述

对于字符串 $T$，定义 $$ T_i = T \left[ i .. \left| T \right| \right] \cdot T \left[ 1 .. i - 1 \right] \quad \left( 1 \leq i \leq \left| T \right| \right) $$

其中 $a \cdot b$ 是字符串 $a$ 与 $b$ 的连接。定义 $f \left( T \right)$ 为最小的 $i$ ($1 \leq i \leq T$) 满足 $T_i = \min \left\{ T_1, T_2, \cdots, T_{\left| T \right|} \right\}$。

给定字符串 $S$，你需要对 $S$ 的每个前缀 $S \left[ 1 .. i \right]$ ($1 \leq i \leq \left| S \right|$)，求出 $f \left( S \left[ 1 .. i \right] \right)$ 的值。

输入格式

共一行，包含一个由小写字母构成的，长度不超过 $3 \times 10^6$ 的字符串。

输出格式

输出一行，包含 $n$ 个整数。其中第 $i$ ($1 \leq i \leq \left| S \right|$) 个整数表示 $f \left( S \left[ 1 .. i \right] \right)$ 的值。

题解

由定义 $f \left( s \right)$ 就是串 $s$ 的最小表示法的下标，如有多个取最小的那个。

单个串的最小表示法可以在 $O \left( n \right)$ 时间内求出，不过并不适用与本题中对所有前缀求最小表示。

在本题中，需要用到在 [ZJOI2017]字符串 中出现过的一个结论：

对于一个字符串 $s$ 以及它的后缀 $v = s \left[ i .. n \right]$，定义 $v$ 是 $s$ 的 "好的" 后缀当且仅当存在字符串 $t$ 满足 $v t$ 是 $s t$ 的最小后缀。则一个长度为 $n$ 的字符串的 "好的" 后缀数量不超过 $\log n$。

证明见那篇题解，这里就不再复读了。

不过，在本题中用这个结论还需要一个引理：

设 $s$ 不是循环串 (i.e. 不存在 $k \geq 2$ 使得 $s = t^k$，此时显然有 $s$ 的最小表示唯一)，设 $s \ll k = s_{k+1} s_{k+2} \cdots s_{\left| s \right|} s_1 s_2 \cdots s_k$ ($0 \leq k < \left| s \right|$) 为 $s$ 的最小表示，则 $s \left[ k + 1 .. n \right]$ 为 "好的" 后缀。

证明

设 $\left| s \right| = n$，且 $s \ll k$ 为 $s$ 的最小表示，取 $t = s \left[ 1 .. k \right]$。下证 $s \left[ k + 1 .. n \right] \cdot s \left[ 1 .. k \right]$ 为 $s \cdot s \left[ 1 .. k \right]$ 的最小后缀。

令 $A = s \left[ 1 .. k \right], B = s \left[ k + 1 .. n \right]$，即证 $B A$ 是 $A B A$ 的最小后缀。

反设不是，假设 $A B A$ 的最小后缀为 $\left( A B A \right) \ll g$。

  1. 若 $0 \leq g < k$，则显然与 $B A = \mathop{\mathrm{minpre}} \left( A B \right)$ 矛盾。

  2. 若 $k < g < n$，由于 $\left( A B A \right) \ll g \neq B A$，因此 $\left( A B A \right) \ll g < B A$。

    而 $\left( A B A \right) \ll g = s \left[ g + 1 .. n \right] \cdot A$，因此 $s \left[ g + 1 .. n \right] \cdot A < B A = s \ll k < s \ll g = s \left[ g + 1 .. n \right] \cdot s \left[ 1 .. g \right]$ (ps: 最后一个小于号是因为 $s$ 非循环串)。

    于是串 $s \left[ g + 1 .. n \right] \cdot s \left[ 1 .. k \right]$ 是串 $s \ll k$ 和串 $s \ll g$ 的一个公共前缀。

    于是在 $s \ll k < s \ll g$ 两端去掉这个 "公共前缀"，得到 $s \ll \left( \left( 2 k - g \right) \bmod n \right) < s \ll k$，与 $s \ll k$ 为最小表示矛盾。

  3. 同理，如果 $n \leq g < n + k$，同样也可以推出矛盾，推理过程类似，这里就省略了。

因此 $B A$ 确实是 $A B A$ 的最小后缀，从而 $s \left[ k + 1 .. n \right]$ 确实是 "好的" 后缀。

因此，我们尝试对于串 $s$ 的每个前缀，维护出它所有 "好的" 后缀的集合，更确切地说，"好的" 后缀的预选集合。这个集合的大小是不会超过当前串长的 $\log$ 的。

这样能不能实现呢？这是可以的。因为每当加入一个字符，可以看成是两个小串合并成一个大串。而右边那个小串其实就是一个单字符 $c$，它的 "好的" 后缀集合显然只有它本身。因此，直接套用那题的合并方法，每次合并的时间复杂度就是 $O \left( \log n \right)$。

最后就只剩下统计答案了。由于那道题中是最小后缀，这道题中是最小表示 (即最小循环表示)，这两个量之间显然是有区别的。(如，串 $\texttt{baa}$ 的最小后缀为 $\texttt a$，最小表示为 $\texttt{aab}$)

我们依然还是把集合中的所有元素扔进去两两比较 (淘汰赛) 得出最终的胜者。

于是我们就需要快速实现两个候选元素的比较。由于 $n \leq 3 \times 10^6$ 且外层已经有了一个 $O \left( \log n \right)$，因此我们希望做到 $O \left( 1 \right)$ 比较 (所以就不能使用 Hash 或后缀数据结构了)。

由那道题中的理论，若一个串中 "好的" 后缀长度从小到大依次为 $s_1, s_2, \cdots, s_k$，则一定有 $s_1 \vartriangleleft s_2 \vartriangleleft \cdots \vartriangleleft s_k$ ($a \vartriangleleft b$ 表示 $a$ 是 $b$ 的非平凡 border)。

因此，集合中任意两个串一定具有前缀关系，从而对于较短的后缀的这段长度，它们一定是相同的。于是我们就需要比较接下来的部分——

  1. 首先是较短的一段已经跳到了开头，较长的那段在走 "尾巴"；

  2. 然后较长的一段也跳到了开头，较短的又走了一段距离，一直跑到它们的起点。

可以发现，两种比较都是原串的一个子串和它本身的比较问题，因此只要能求出原串的每个后缀和它本身的 LCP 即可，而这恰恰就是 Z-Algorithm (扩展 KMP) 所干的事情，可以 $O \left( n \right)$ 预处理，$O \left( 1 \right)$ 查询。

总时间复杂度 $O \left( n \log n \right)$。

代码

#include <bits/stdc++.h>
using std::cin;
using std::cout;

const int N = 3000054;

int n, Cur, Next;
int z[N];
int buf[2][24], *cur = *buf, *nxt = buf[1];
char s[N];

void Z() {
	int i, Max = 0, M = 0;
	for (i = 1; i < n; ++i) {
		z[i] = (i < Max ? std::min(z[i - M], Max - i) : 0);
		for (; s[z[i]] == s[i + z[i]]; ++z[i]);
		if (i + z[i] > Max) Max = i + z[i], M = i;
	}
}

inline int cmp0x(int x, int len) {return z[x] >= len ? 0 : (int)s[z[x]] - (int)s[x + z[x]];}

inline int cyccmp(int l, int r, int cyc) {
	assert(l < r);
	int c = cmp0x(cyc - (r - l), r - l);
	return c ? -c : cmp0x(r - l, l);
}

int main() {
	int i, j, c, u, v, ans;
	std::ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> s, n = strlen(s), Z();
	cout.put(49), Next = 1;
	for (i = 1; i < n; ++i) {
		std::swap(cur, nxt), std::swap(Cur, Next), *nxt = i, Next = 1;
		for (j = 0; j < Cur; ++j) for (; ; ) {
			u = cur[j], v = nxt[Next - 1];
			if ((c = (int)s[u + (i - v)] - (int)s[i]) > 0) break;
			if (!c) {Next -= (i + 1 - v) * 2 > i + 1 - u, nxt[Next++] = u; break;}
			if (!--Next) {nxt[Next++] = u; break;}
		}
		for (ans = *nxt, j = 1; j < Next; ++j) cyccmp(nxt[j], ans, i + 1) <= 0 && (ans = nxt[j]);
		cout << ' ' << ++ans;
	}
	return cout.put(10), 0;
}

坑

坑1：判断两倍的时候注意当前串的长度为 $i + 1$ 以及取等问题，不要错了边界数据。

坑2：在本题中，比较的时候不能暴力比较，要利用互为前缀的性质，只比较最后一个字符 (新加进来的字符)。