「Codeforces 1063F」String Journey

第一篇算法相关

第一次自己想sam

Codeforces 1063F

题意

给出一个长度为\(n\)的字符串\(s\)。

如果一个字符串序列\(t_1,\dotsc,t_k\)，\(\forall1<i\le k\)，\(t_i\)是\(t_{i-1}\)的一个子串，且长度严格小，那么称这个字符串序列是一个journey。

一个journey的长度是其中字符串的数量

求最长的journey，满足存在字符串序列\(u_1,\dotsc,u_{k+1}\)(可以为空)，使\(s=u_1t_1u_2t_2\cdots u_kt_ku_{k+1}\)。

---

分析

• 观察：存在最长的journey \(t\)，满足\(|t_i|=|t_{i-1}|-1\)，即长度每次减少1

显然

这可以通过删减一定字符得到

• 观察：若存在以\(s\)中的第\(i\)个位置开头的长度为\(k\)的journey，那么存在以该位置开头的长度为\(t，1\le t\le k\)的journey

这也可以删除一定字符得到

然后考虑从右向左dp，令\(f_i\)表示以\(s\)中第\(i\)个位置开头的最长的journey的长度。

\(f_i\)是可以二分的，但是并不好检验

• 观察：\(f_{i+1}\ge f_i-1\)

这也可以通过删除一定字符得到

移项得\(f_i\le f_{i+1}+1\)

因此不需要二分，由于均摊的性质，直接推下来，总检验次数是线性的

• 观察：在dp过程中，能被转移的位置\((\ge i+f_i-1)\)单调不严格左移

1. 在从\(i+1\)转移到\(i\)时，能被转移的位置不变：\(i+f_i=i+f_{i+1}-1=(i+1)+f_{i+1}\)

2. 在检验\(f_i\)失败的时候，\(f_i\)减小，\(i+f_i-1\)也减小

于是需要数据结构维护

1. 插入一个位置

2. 检验是否有位置\(j\)与当前的\(i\)满足最长公共前缀\(lcp(s[i..n],s[j..n])\ge f_i-1\)，且\(f_j\ge f_i-1\)

---

考虑使用sam+线段树

对\(s\)的反串建sam，插入一个位置\(p\)的时候，从这个位置对应的parent树终止节点向上跳到最深的一个能表示出长度\(f_p\)的节点\(u\)，(\(len_u\ge f_p\)，\(len_u\)表示\(u\)能表示的最长字符串)。

\(u\)子树中所有的节点表示的串和\(u\)的最长公共前缀\(\ge f_p-1\)。

并且对于\(u\)的任意祖先\(v\)，\(v\)的子树中所有节点表示的串和\(u\)的最长公共前缀\(\ge len_v\)。

这些可以转化到dfs序上的区间取max，用线段树维护

而检验一个\(f_p\)的时候只要查询覆盖i对应的终止节点处的最大值是否\(\ge f_p-1\)

考虑到更新\(u\)的祖先\(v\)的时候复杂度并不优秀，但是更新的值是\(len_v\)，这只和\(v\)自身有关，打个标记避免重复，可以做到\(\mathcal O(n)\)次

字符集大小为常数，总复杂度\(\mathcal O(n\log n)\)

---

代码

#include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<vector>

using namespace std;
#define ll long long
const int N = 500005;
int n, cnt, last, pl, pr, idfn, ans, f[N], g[N], dfn[N<<1], rdfn[N<<1], fa[N<<1], len[N<<1], w[N<<3], ch[N<<1][26];
bool vis[N<<1];
char s[N];
vector<int> e[N<<1];
inline void extend(int c){
	int p=last, np=++cnt;
	last=cnt, len[np]=len[p]+1;
	while(p && !ch[p][c]) ch[p][c]=np, p=fa[p];
	if(!p) fa[np]=1;
	else{
		int q=ch[p][c];
		if(len[q]==len[p]+1) fa[np]=q;
		else{
			int nq=++cnt;
			len[nq]=len[p]+1, memcpy(ch[nq], ch[q], 26<<2);
			fa[nq]=fa[q], fa[q]=fa[np]=nq;
			while(ch[p][c]==q) ch[p][c]=nq, p=fa[p];
		}
	}
}
void change(int l, int r, int t, int L, int R, int x){
	if(L<=l && r<=R) return (void)(w[t]=max(w[t], x));
	int mid=l+r>>1, k=t<<1;
	if(L<=mid) change(l, mid, k, L, R, x);
	if(R>mid) change(mid+1, r, k|1, L, R, x);
}
int query(int l, int r, int t, int x){
	if(l==r) return w[t];
	int mid=l+r>>1, k=t<<1;
	return max(w[t], x<=mid?query(l, mid, k, x):query(mid+1, r, k|1, x));
}
inline bool check(int x){
	return query(1, cnt, 1, dfn[pl])>=x-1 || query(1, cnt, 1, dfn[pr])>=x-1;
}
inline void dfs(int x){
	dfn[x]=++idfn;
	for(int i:e[x]) dfs(i);
	rdfn[x]=idfn;
}
inline void solve(int x){
	if(vis[x] || x<=1) return;
	vis[x]=1;
	change(1, cnt, 1, dfn[x], rdfn[x], len[x]);
	solve(fa[x]);
}
int main() {
	scanf("%d%s", &n, s+1);
	last=cnt=1;
	for(int i=n; i; --i) extend(s[i]-'a');
	for(int i=2; i<=cnt; ++i) e[fa[i]].push_back(i);
	dfs(1);
	g[n+1]=pl=pr=1;
	for(int i=n; i; --i){
		pr=pl, pl=ch[pl][s[i]-'a'];

		f[i]=f[i+1]+1;
		while(!check(f[i])){
			--f[i];
			change(1, cnt, 1, dfn[g[i+f[i]]], rdfn[g[i+f[i]]], f[i+f[i]]);
			solve(fa[g[i+f[i]]]);
		}
		ans=max(ans, f[i]);
		g[i]=ch[g[i+1]][s[i]-'a'];
		while(len[fa[g[i]]]>=f[i]) g[i]=fa[g[i]];
	}
	return printf("%d", ans), 0;
}