Substring selection / String Journey

Title Link: YBT2022 winter vacation Day6 C / luogu CF1063F

General idea of the topic

Give you a string. If you want to find the maximum K satisfaction, you can choose k disjoint substrings from left to right at a time to meet that the former is the real substring of the latter.

thinking

First of all, let's consider a little greed. The length of each substring must be reduced by one. Then the length is: x , x − 1 , x − 2 , . . . , 2 , 1 x,x-1,x-2,...,2,1 x,x−1,x−2,...,2,1

I wasn't sure at first. It's not easy to do. Consider turning it over, and then 1 , 2 , . . . , x 1,2,...,x 1,2,...,x.

Then there is a property here, which is f i + 1 ⩽ f i + 1 f_{i+1}\leqslant f_{i}+1 fi+1​⩽fi​+1.
Simply prove that the transfer is obtained f i + 1 − 1 ⩽ f i f_{i+1}-1\leqslant f_{i} fi+1 − 1 ⩽ fi i + 1 i+1 Subtract the first character from all the i+1 positions to construct a i i i position, and then delete only one, so subtract one.

Then you can consider this, every time we assume f i = f i − 1 + 1 f_i=f_{i-1}+1 Fi = fi − 1 + 1, and then constantly judge whether it is feasible. Obviously, the complexity will only judge about n n n times.

That's the judgment part. We need to find out whether it exists j j j make j ∼ j + f i − 2 j\sim j+f_i-2 J ∼ j+fi − 2 yes i ∼ i + f i − 1 i\sim i+f_i-1 i ∼ i+fi − 1.
Then because the length difference is only 1 1 1. Therefore, there are only two possibilities: prefix or suffix.

Then we consider using SAM to find the overlapping part, that is, we want the coincidence degree to reach f i − 1 f_i-1 fi​−1.
There's another problem, that is, don't hand it in, you need to j < i − f i + 1 j<i-f_i+1 j<i−fi​+1.

Then you can consider scanning with a pointer. Why? Because i − f i + 1 i-f_i+1 i − fi + 1 is incremental.
every time f i f_i fi at most plus one j j j also increases by one, so it will not decrease, but increase, so we can maintain it with pointers.

Then as for which transfer to use, we can use segment tree.
Because you need to ensure that it is a substring, we find the son of the corresponding point on the parent tree made by SAM.
The information in this son uses the line segment tree to find the position of this point on SAM, and you can jump to it with multiplication l e n = f i − 1 len=f_i-1 len=fi − 1 position.

Then you can.

code

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

int n, f[500001], pl[500001];
char s[500001];

struct node {
	int son[31], fa, len;
}d[1000005];
int lst, tot;
vector <int> e[1000005];

void SAM_insert(int x) {
	int p = lst, np = ++tot; lst = np;
	d[np].len = d[p].len + 1;
	for (; p && !d[p].son[x]; p = d[p].fa) d[p].son[x] = np;
	if (!p) d[np].fa = 1;
		else {
			int q = d[p].son[x];
			if (d[q].len == d[p].len + 1) d[np].fa = q;
				else {
					int nq = ++tot;
					d[nq] = d[q];
					d[nq].len = d[p].len + 1;
					d[np].fa = d[q].fa = nq;
					for (; p && d[p].son[x] == q; p = d[p].fa) d[p].son[x] = nq;
				}
		}
}

int fa[1000005][21], dfnn;
int dfn[1000005], ed[1000005];

void dfs(int now) {
	dfn[now] = ++dfnn;
	for (int i = 1; i <= 20; i++)
		fa[now][i] = fa[fa[now][i - 1]][i - 1];
	for (int i = 0; i < e[now].size(); i++) {
		int x = e[now][i];
		fa[x][0] = now; dfs(x);
	}
	ed[now] = dfnn;
}

struct XD_tree {
	int val[1000005 << 2];
	
	void up(int now) {
		val[now] = max(val[now << 1], val[now << 1 | 1]);
	}
	
	void insert(int now, int l, int r, int pl, int va) {
		if (l == r) {
			val[now] = va; return ;
		}
		int mid = (l + r) >> 1;
		if (pl <= mid) insert(now << 1, l, mid, pl, va);
			else insert(now << 1 | 1, mid + 1, r, pl, va);
		up(now);
	}
	
	int query(int now, int l, int r, int L, int R) {
		if (L <= l && r <= R) return val[now];
		int mid = (l + r) >> 1, re = 0;
		if (L <= mid) re = query(now << 1, l, mid, L, R);
		if (mid < R) re = max(re, query(now << 1 | 1, mid + 1, r, L, R));
		return re;
	}
}T;

int jump(int now, int k) {
	if (!now) return 0;
	for (int i = 20; i >= 0; i--)
		if (d[fa[now][i]].len >= k)
			now = fa[now][i];
	return now;
}

bool check(int i) {
	int p1 = jump(pl[i], f[i] - 1);
	int p2 = jump(pl[i - 1], f[i] - 1);
	return (max(p1 ? T.query(1, 1, dfnn, dfn[p1], ed[p1]) : -1, p2 ? T.query(1, 1, dfnn, dfn[p2], ed[p2]) : -1) >= (f[i] - 1));
}

int main() {
	scanf("%d", &n);
	scanf("%s", s + 1);
	
	reverse(s + 1, s + n + 1);
	lst = tot = 1; d[0].len = -1;
	for (int i = 1; i <= n; i++) {
		SAM_insert(s[i] - 'a');
		pl[i] = lst;
	}
	for (int i = 2; i <= tot; i++)
		e[d[i].fa].push_back(i);
	dfs(1);
	
	int ans = 0, R = 0;
	for (int i = 1; i <= n; i++) {
		f[i] = f[i - 1] + 1;
		while (!check(i)) {
			f[i]--; R++;
			T.insert(1, 1, dfnn, dfn[pl[R]], f[R]);
		}
		ans = max(ans, f[i]);
	}
	printf("%d", ans);
	
	return 0;
}