CF700E Cool Slogans 题解

CF700E Cool Slogans

题意

• 给定一个长度为 $n$ 的字符串 $s$。
• 你要构造一个最长的字符串序列 $t_{1\dots k}$，满足：
  1. 对于 $i \in [1,k]$，$t_i$ 为 $s$ 的子串。
  2. 对于 $i \in [2,k]$，$t_i$ 在 $t_{i-1}$ 中出现了至少两次。
• $n \le 2 \times 10^5$。

题解

对字符串建 SAM，用（可持久化）线段树合并求出每个节点的 $\operatorname{endpos}$ 集合。

在 $\operatorname{parent}$ 树上从根向下 dp，设 $f_i$ 表示到节点 $i$ 时的最大值。

如果一个父节点的子串在子节点的子串中出现了至少两次，则转移时 $f$ 加一，否则不变。

考虑如何判断是否出现了至少两次，设此时的子节点为 $x$，父节点为 $pa_x$。

找到 $x$ 对应的 $\operatorname{endpos}$ 中的任意一个位置 $pos$，则 $pos$ 处 $pa_x$ 的子串一定出现了一次。

那么另一次只要在 $[pos - \operatorname{len}(x) + \operatorname{len}(pa_x), pos - 1]$ 中有出现就行了。

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

代码

const int N = 2e5 + 7;
struct T {
	int l, r;
} t[N<<6|1];
int rt[N<<1], f[N<<1], g[N<<1], tot, ans = 1;

int insert(int l, int r, int x) {
	int p = ++tot;
	if (l == r) return p;
	int mid = (l + r) >> 1;
	if (x <= mid) t[p].l = insert(l, mid, x);
	else t[p].r = insert(mid + 1, r, x);
	return p;
}

int merge(int p, int q) {
	if (!p || !q) return p | q;
	int o = ++tot;
	t[o].l = merge(t[p].l, t[q].l);
	t[o].r = merge(t[p].r, t[q].r);
	return o;
}

bool ask(int p, int l, int r, int L, int R) {
	if (!p) return 0;
	if (L <= l && R >= r) return 1;
	int mid = (l + r) >> 1;
	if (L <= mid && ask(t[p].l, l, mid, L, R)) return 1;
	if (R > mid && ask(t[p].r, mid + 1, r, L, R)) return 1;
	return 0;
}

struct SAM {
	int n, l, ch[N<<1][26], len[N<<1], pa[N<<1], t;
	char s[N];
	int pos[N<<1];
	inline void init() { pa[0] = -1; }
	inline void add(int c, int o) {
		int w = ++t, p = l;
		len[w] = len[l] + 1, pos[w] = o;
		while (~p && !ch[p][c]) ch[p][c] = w, p = pa[p];
		if (!~p) return pa[l=w] = 0, void();
		int q = ch[p][c];
		if (len[p] + 1 == len[q]) return pa[l=w] = q, void();
		int k = ++t;
		pa[k] = pa[q], pos[k] = pos[q], memcpy(ch[k], ch[q], sizeof(ch[k]));
		len[k] = len[p] + 1, pa[w] = pa[q] = k;
		while (~p && ch[p][c] == q) ch[p][c] = k, p = pa[p];
		l = w;
	}
	inline void build() {
		init();
		for (int i = 1; i <= n; i++) add(s[i] - 'a', i);
	}
	int b[N<<1], c[N];
	inline void sort() {
		for (int i = 1; i <= t; i++) ++c[len[i]];
		for (int i = 1; i <= n; i++) c[i] += c[i-1];
		for (int i = 1; i <= t; i++) b[c[len[i]]--] = i;
	}
	inline void work() {
		for (int i = 1, p = 0; i <= n; i++)
			p = ch[p][s[i]-'a'], rt[p] = insert(1, n, i);
		for (int i = t; i; i--)
			rt[pa[b[i]]] = merge(rt[pa[b[i]]], rt[b[i]]);
		for (int i = 1; i <= t; i++) {
			int x = b[i];
			if (!pa[x]) {
				f[x] = 1, g[x] = x;
				continue;
			}
			if (ask(rt[g[pa[x]]], 1, n, pos[x] - len[x] + len[g[pa[x]]], pos[x] - 1))
				f[x] = f[pa[x]] + 1, g[x] = x;
			else f[x] = f[pa[x]], g[x] = g[pa[x]];
			ans = max(ans, f[x]);
		}
	}
} sam;

int main() {
	rd(sam.n), rds(sam.s, sam.n), sam.build();
	sam.sort(), sam.work(), print(ans);
	return 0;
}