「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)\)


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#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;
}
0%