Codeforces 700E Cool Slogans

发表于 | 分类于 | 23

一个挺妙的 DP 题（

两个结论：

第一，满足对于 2≤i≤k，si−1 是 si 的后缀的一个答案一定是最优解之一。
证明：若不满足，则将 si 中，si−1 第一次出现的位置删去，下一步的决策显然不会变少，即答案不会变劣。

第二，在 Parent Tree 上，某个祖先的所有字符串在这个状态的所有字符串的匹配情况相同。
证明就不写了，这个用 endpos 等价类的性质不难证明。

那么就有方案了：在 Parent Tree 上，从根向下 DP，每个状态向上找最近的一个在当前链最优解中的状态，看其是否能在该状态内匹配两次（即除了作为后缀还有另一次，这个可以通过线段树合并维护 endpos 来维护）。
如果可以就加入最优解，否则直接跳过，这个状态便是对答案无用的。

然而往上找的过程，如果倍增的话需要 O(nlog2n)。
虽然也能过，但是实际上直接在 DP 过程中即可维护这个需要的状态。
O(nlogn) 即可。

代码： 

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
#include <cstdio>
#include <cstring>
#include <algorithm>
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);
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment