一个挺妙的 DP 题（
两个结论：
第一，满足对于 \(2 \le i \le k\)，\(s_{i-1}\) 是 \(s_i\) 的后缀的一个答案一定是最优解之一。
证明：若不满足，则将 \(s_i\) 中，\(s_{i-1}\) 第一次出现的位置删去，下一步的决策显然不会变少，即答案不会变劣。
第二，在 Parent Tree 上，某个祖先的所有字符串在这个状态的所有字符串的匹配情况相同。
证明就不写了，这个用 \(\rm endpos\) 等价类的性质不难证明。
那么就有方案了：在 Parent Tree 上，从根向下 DP，每个状态向上找最近的一个在当前链最优解中的状态，看其是否能在该状态内匹配两次（即除了作为后缀还有另一次，这个可以通过线段树合并维护 \(\rm endpos\) 来维护）。
如果可以就加入最优解，否则直接跳过，这个状态便是对答案无用的。
然而往上找的过程，如果倍增的话需要 \(O(n \log^2 n)\)。
虽然也能过，但是实际上直接在 DP 过程中即可维护这个需要的状态。
\(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
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
using namespace std;
const int N = 2e5;
int n;
char s[N + 5];
int ans;
namespace SEG
{
struct node
{
int ls,rs;
} seg[(N << 6) + 10];
int seg_tot;
void insert(int x,int &p,int tl,int tr)
{
int &tot = seg_tot;
!p && (p = ++tot);
if(tl == tr)
return ;
int mid = tl + tr >> 1;
x <= mid ? insert(x,seg[p].ls,tl,mid) : insert(x,seg[p].rs,mid + 1,tr);
}
int merge(int x,int y)
{
if(!x || !y)
return x | y;
int &tot = seg_tot;
int p = ++tot;
seg[p].ls = merge(seg[x].ls,seg[y].ls),seg[p].rs = merge(seg[x].rs,seg[y].rs);
return p;
}
int query(int l,int r,int p,int tl,int tr)
{
if(!p)
return 0;
if(l <= tl && tr <= r)
return 1;
int mid = tl + tr >> 1;
if(l <= mid && query(l,r,seg[p].ls,tl,mid))
return 1;
if(r > mid && query(l,r,seg[p].rs,mid + 1,tr))
return 1;
return 0;
}
}
namespace SAM
{
struct node
{
int ch[26];
int fa,len,suf,rt,r;
} sam[(N << 1) + 5];
int las = 1,tot = 1;
int c[N + 5],a[(N << 1) + 5];
int f[(N << 1) + 5],g[(N << 1) + 5];
inline void insert(int x)
{
int cur = las,p = ++tot;
sam[p].r = sam[p].len = sam[cur].len + 1,sam[p].suf = 1;
for(;cur && !sam[cur].ch[x];cur = sam[cur].fa)
sam[cur].ch[x] = p;
if(!cur)
sam[p].fa = 1;
else
{
int q = sam[cur].ch[x];
if(sam[cur].len + 1 == sam[q].len)
sam[p].fa = q;
else
{
int nxt = ++tot;
sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt,sam[nxt].suf = 0;
for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
sam[cur].ch[x] = nxt;
}
}
las = p;
}
inline void build()
{
for(register int i = 1;i <= n;++i)
insert(s[i] - 'a');
for(register int i = 1;i <= tot;++i)
++c[sam[i].len];
for(register int i = 1;i <= n;++i)
c[i] += c[i - 1];
for(register int i = tot;i > 1;--i)
a[c[sam[i].len]--] = i;
for(register int i = tot;i > 1;--i)
sam[a[i]].suf && (SEG::insert(sam[a[i]].len,sam[a[i]].rt,1,n),1),sam[sam[a[i]].fa].rt = SEG::merge(sam[sam[a[i]].fa].rt,sam[a[i]].rt);
for(register int i = 2;i <= tot;++i)
{
if(sam[a[i]].fa == 1 || SEG::query(sam[a[i]].r - sam[a[i]].len + sam[g[sam[a[i]].fa]].len,sam[a[i]].r - 1,sam[g[sam[a[i]].fa]].rt,1,n))
f[a[i]] = f[sam[a[i]].fa] + 1,g[a[i]] = a[i];
else
f[a[i]] = f[sam[a[i]].fa],g[a[i]] = g[sam[a[i]].fa];
ans = max(ans,f[a[i]]);
}
}
}
int main()
{
scanf("%d%s",&n,s + 1);
SAM::build();
printf("%d\n",ans);
}