[CF700E]后缀自动机+线段树合并

题目大意

给定一个字符串 $S$,要求构造字符串序列 $s_1,s_2,\ldots,s_k$,满足任意 $s_i$ 都是 $S$ 的子串,且任意 $i\in[2,n]$,都有 $s_i$ 在 $s_{i-1}$ 中出现了至少 2 次(可以有重叠部分,只要起始、结尾位置不同即可)。

求可能的最大的 $k$ 的值(即序列的最大可能长度)。

思路

首先我们知道如果子串 $a$ 在子串 $b$ 中出现超过两次,那么我们可以只需要保证 $a$ 是 $b$ 的后缀即可(如果 $a$ 不是 $b$ 的后缀,那么 $b$ 可以删去后面的一部分使得 $b$ 更短,这样 $b$ 就更可能匹配上其它的串)

因为 $a$ 是 $b$ 的后缀,那么 $a$ 一定是 $b$ 在SAM的Fail树上祖先,所以可以考虑DP

令 $f_i$ 表示以 $i$ 点或 $i$ 点的祖先为最长串的最大的 $k$ 的值, $g_i$ 表示最长串是哪一个点

这样DP过程就是自根向下,假设当前为 $i$ 点,如果 $g_{fail_i}$ 在 $i$ 中出现了至少 2 次,那么 $f_i=f_{fail_i}+1,g_i=i$ 否则 $f_i=f_{fail_i},g_i=g_{fail_i}$

接下来考虑如何子串 $a$ 是否在子串 $b$ 中出现超过两次

首先若子串 $a$ 是子串 $b$ 的祖先时子串 $a$ 一定在子串 $b$ 中出现过一次

那么我们只需要考虑子串 $a$ 是否在子串 $b$ 中再出现一次

考虑我们知道 $a,b$ 的 $Endpos$ 集合,那么对于 $b$ 中 $Endpos$ 集合中的任何一个点(设其为 $x$ ) ,必定满足子串 $a$ 的 $Endpos$ 集合中有至少一点在 $[x-len[b]+len[a],x-1]$ 中

所以可以用线段树合并维护 $Endpos$ 集合即可

代码

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
/***************************************************************
File name: CF700E.cpp
Author: ljfcnyali
Create time: 2020年01月12日 星期日 19时05分49秒
***************************************************************/
#include<bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for ( int i = (a), _end_ = (b); i <= _end_; ++ i )
#define mem(a) memset ( (a), 0, sizeof ( a ) )
#define str(a) strlen ( a )
#define pii pair<int, int>
#define ls(x) Tree[x].lson
#define rs(x) Tree[x].rson
typedef long long LL;

const int maxn = 1e6 + 10;

int n, last = 1, tot = 1, Begin[maxn], Next[maxn], To[maxn], e, ans;
int anc[maxn][22], Root[maxn], cnt, f[maxn], Max[maxn], g[maxn];
struct node1 { int Next[26], len, fa; } Trie[maxn];
struct node2 { int lson, rson, sum; } Tree[maxn << 4];
char s[maxn];

inline void Modify(int &root, int l, int r, int pos)
{
if ( !root ) root = ++ cnt;
++ Tree[root].sum;
if ( l == r ) return ;
int Mid = l + r >> 1;
if ( pos <= Mid ) Modify(ls(root), l, Mid, pos);
else Modify(rs(root), Mid + 1, r, pos);
}

inline int Merge(int p, int q, int l, int r)
{
if ( !p || !q ) return p + q;
int root = ++ cnt;
Tree[root].sum = Tree[p].sum + Tree[q].sum;
if ( l == r ) return root;
int Mid = l + r >> 1;
ls(root) = Merge(ls(p), ls(q), l, Mid);
rs(root) = Merge(rs(p), rs(q), Mid + 1, r);
return root;
}

inline int Query(int root, int l, int r, int L, int R)
{
if ( !root ) return 0;
if ( L <= l && r <= R ) return Tree[root].sum;
int Mid = l + r >> 1, ret = 0;
if ( L <= Mid ) ret += Query(ls(root), l, Mid, L, R);
if ( Mid < R ) ret += Query(rs(root), Mid + 1, r, L, R);
return ret;
}

inline void add(int u, int v) { To[++ e] = v; Next[e] = Begin[u]; Begin[u] = e; }

inline void Extand(int c, int x)
{
int cur = ++ tot; Trie[cur].len = Trie[last].len + 1;
Modify(Root[cur], 1, n, x); Max[cur] = x;
int p = last; last = cur;
while ( p && !Trie[p].Next[c] ) { Trie[p].Next[c] = cur; p = Trie[p].fa; }
if ( !p ) { Trie[cur].fa = 1; return ; }
int q = Trie[p].Next[c];
if ( Trie[p].len + 1 == Trie[q].len ) { Trie[cur].fa = q; return ; }
int clone = ++ tot; Trie[clone] = Trie[q]; Trie[clone].len = Trie[p].len + 1;
while ( p && Trie[p].Next[c] == q ) { Trie[p].Next[c] = clone; p = Trie[p].fa; }
Trie[cur].fa = Trie[q].fa = clone;
}

inline void DFS1(int u)
{
for ( int i = Begin[u]; i; i = Next[i] )
{
int v = To[i]; anc[v][0] = u; DFS1(v);
if ( u != 1 ) { Max[u] = max(Max[u], Max[v]); Root[u] = Merge(Root[u], Root[v], 1, n); }
}
}

inline void DFS2(int u)
{
for ( int i = Begin[u]; i; i = Next[i] )
{
int v = To[i];
if ( u == 1 )
{
f[v] = 1; g[v] = v;
}
else if ( Query(Root[g[u]], 1, n, Max[v] - Trie[v].len + Trie[g[u]].len, Max[v] - 1) )
{
f[v] = f[u] + 1; g[v] = v;
}
else { f[v] = f[u]; g[v] = g[u]; }
DFS2(v);
}
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
scanf("%d", &n);
scanf("%s", s + 1);
REP(i, 1, n) Extand(s[i] - 'a', i);
REP(i, 2, tot) add(Trie[i].fa, i);
DFS1(1);
REP(j, 1, 20) REP(i, 1, n) anc[i][j] = anc[anc[i][j - 1]][j - 1];
f[1] = g[1] = 1; DFS2(1);
REP(i, 1, tot) ans = max(ans, f[i]);
printf("%d\n", ans);
return 0;
}