0%

「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;
}