CTime_Pup_314

不能再颓废了

0%

CF700E Cool Slogans

发表于 更新于 分类于 阅读次数： Valine：

题面描述

求最长子串序列使得后一个在前一个出现至少 \(2\) 次

题解

子串序列显然属于 \(Parent\) 树从根节点到叶子节点的链上，考虑 \(Parent\) 树上 \(DP\)

但是，答案是最长的一条链吗？

自己多试几组发现并不是如此，比如 \(abababb\) 中 \(parent(ab) = a\) 但并没有出现两次

本题的关键在于此

首先，不难证明一个结论 \(A\) 的最长串 \(S\) 被\(Parent\) 树上的祖先 \(B\) 的任意 \(S'\) 匹配状态相同，所以选最长串作为序列即可 对于一个 \(endpos\) 集合，只要其中 \(1\) 个合法，其他都合法，所以只需判断一次即可，具体来说，设 \(parent(A) = B\)，若 \(p\in endpos(B)\cap [pos(A)-len(A)+len(B),\ pos(B)-1]\) 则出现两次

线段树合并搞一下就好了

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 4e5+5;
int last = 1, sam_tot = 1, fa[N], ch[N][26], size[N], len[N], pos[N];
int tax[N], p[N];
void samAdd(int c)
{
    int cur = ++sam_tot, pre = last; last = sam_tot;
    len[cur] = len[pre]+1; pos[cur] = len[cur];
    while(pre&&!ch[pre][c]) ch[pre][c] = cur, pre = fa[pre];
    if(!pre) return void(fa[cur] = 1);
    int x = ch[pre][c];
    if(len[pre]+1 == len[x]) return void(fa[cur] = x);
    int y = ++sam_tot; fa[y] = fa[x]; pos[y] = pos[x];
    len[y] = len[pre]+1; fa[x] = fa[cur] = y; 
    memcpy(ch[y], ch[x], sizeof(ch[x]));
    while(pre&&ch[pre][c] == x) ch[pre][c] = y, pre = fa[pre];
}
int n, f[N], top[N];
char s[N];

int seg_tot, root[N], ls[N<<6], rs[N<<6], val[N<<6], ans;
int merge(int x, int y)
{
    if(!x||!y) return x|y;
    int z = ++seg_tot;
    val[z] = val[x]+val[y];
    ls[z] = merge(ls[x], ls[y]);
    rs[z] = merge(rs[x], rs[y]);
    return z;
}
void add(int &x, int l, int r, int pos)
{
    if(!x) x = ++seg_tot; ++val[x];
    if(l == r) return;
    int mid = (l+r)>>1;
    if(pos <= mid) add(ls[x], l, mid, pos);
    else add(rs[x], mid+1, r, pos);
}
bool query(int x, int l, int r, int ql, int qr)
{
    if(!x||(ql <= l&&r <= qr)) return val[x];
    int mid = (l+r)>>1; bool ret = false;
    if(ql <= mid) ret |= query(ls[x], l, mid, ql, qr);
    if(qr > mid) ret |= query(rs[x], mid+1, r, ql, qr);
    return ret;   
}
int main()
{
    scanf("%d%s", &n, s+1); 
    for(int i = 1; i <= n; ++i) add(root[sam_tot+1], 1, n, i), samAdd(s[i]-'a');
    for(int i = 1; i <= sam_tot; ++i) ++tax[len[i]];
    for(int i = 1; i <= sam_tot; ++i) tax[i] += tax[i-1];
    for(int i = 1; i <= sam_tot; ++i) p[tax[len[i]]--] = i;
    for(int i = sam_tot; i > 1; --i) root[fa[p[i]]] = merge(root[fa[p[i]]], root[p[i]]);
    for(int i = 2; i <= sam_tot; ++i)
    {
        int x = p[i]; 
        if(fa[x] == 1) f[x] = 1, top[x] = x;
        else
        {
            if(query(root[top[fa[x]]], 1, n, pos[x]-len[x]+len[top[fa[x]]], pos[x]-1)) f[x] = f[top[fa[x]]]+1, top[x] = x;
            else f[x] = f[top[fa[x]]], top[x] = top[fa[x]];
        }
        ans = max(ans, f[x]);
    }
    printf("%d\n", ans);
    return 0;
}