「CF700E」Cool Slogans

    「CF700E」Cool Slogans

    CF700E

    给出一个长度为 nn 的字符串 str\mathrm{str}。你需要构造一个尽量字符串序列 s1,s2,⋯ ,sks_1, s_2, \cdots, s_k,满足:

    • 对于任意 1≤i≤n1 \leq i \leq n,sis_i 为 str\mathrm{str} 的子串。
    • 对于任意 1<i≤n1 < i \leq n,si−1s_{i - 1} 在 sis_i 中至少出现了两次(可重叠)。

    只需求出 kk 的最大值即可。

    数据范围:1≤n≤2×1051 \leq n \leq 2 \times 10^5。

    时空限制:44s / 500500MiB。

    Solution

    引理 1

    一定存在一种最优方案,使得 si−1s_{i - 1} 为 sis_i 的 border。

    证明

    对于一个串 sis_i,将其首尾多余的部分去掉,此时 sis_i 即为 si−1s_{i - 1} 的 border。按 ii 从小到大将 sis_i 的多余部分去掉即可得到满足该性质的方案。

    根据「引理 1」,可以得知 si−1s_{i - 1} 为 sis_i 的严格后缀。考虑将原串的 SAM 建出。

    引理 2

    在 SAM 的 parent 树上,对于任意一个状态 xx 与其祖先状态 yy,yy 表示的所有子串在 xx 表示的最长串的出现次数相同。

    证明

    P2.png

    反证法,考虑如图所示的子串结构。串 SS 是状态 xx 所表示的最长串;串 T1,T2T_1, T_2 是状态 yy 所表示的任意两个子串,这两个子串在 SS 中的出现次数不同,必然会出现如图所示的结构。此时可以构造一个串 S′S' 来使得 T1,T2T_1, T_2 在 S′S' 中的出现次数相同。

    由于 endpos(x)⫋endpos(y)\mathrm{endpos}(x) \subsetneqq \mathrm{endpos}(y),则出现 SS 的地方,前面总会跟着一个串 T2T_2。这样的话会使得 S,T2S, T_2 组合成一个 S′S',可以推出 endpos(S)=endpos(S′)\mathrm{endpos}(S) = \mathrm{endpos}(S'),这与 SS 为状态 xx 所表示的最长串矛盾,故假设不成立。

    Q.E.D

    根据「引理 2」,可以得知对于 SAM 的每个状态,我们都只需要记录其所表示的最长串的等级信息即可。

    此时就可以在 parent 树上 dp,设 fif_i 表示从根到节点 ii 的最大等级,设 gig_i 表示从根到节点 ii 最大等级串的状态编号。

    • 若 xx 所表示的最长串中出现了两次 gFaxg_{\mathrm{Fa}_x} 所表示的最长串,则
    fx=fFax+1gx=xf_x = f_{{\mathrm{Fa}_x}} + 1 \\g_x = x
    • 否则
    fx=fFaxgx=gFaxf_x = f_{\mathrm{Fa}_x} \\g_x = g_{\mathrm{Fa}_x}

    运用可持久化线段树合并维护 endpos\mathrm{endpos} 集合,来判断每次是否可以成功转移。

    时间复杂度 O(nlog⁡n)\mathcal{O}(n \log n)。

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    const int N = 200100;
    
    int n;
    char str[N];
    
    namespace SGT {
        const int SIZE = 10001000;
    
        int cT;
        struct node {
            int lc, rc;
        } t[SIZE];
    
        void insert(int &p, int l, int r, int x) {
            p = ++ cT;
            if (l == r) return;
            int mid = (l + r) >> 1;
            if (x <= mid)
                insert(t[p].lc, l, mid, x);
            else
                insert(t[p].rc, mid + 1, r, x);
        }
    
        int merge(int p, int q) {
            if (!p || !q) return p ^ q;
            int x = ++ cT;
            t[x].lc = merge(t[p].lc, t[q].lc);
            t[x].rc = merge(t[p].rc, t[q].rc);
            return x;
        }
    
        bool ask(int p, int l, int r, int s, int e) {
            if (!p) return 0;
            if (s <= l && r <= e) return 1;
            int mid = (l + r) >> 1;
            if (s <= mid && ask(t[p].lc, l, mid, s, e)) return 1;
            if (mid < e && ask(t[p].rc, mid + 1, r, s, e)) return 1;
            return 0;
        }
    }
    
    int ans;
    
    namespace SAM {
        const int SIZE = N * 2; 
    
        int cT = 1, Last = 1;
        struct node {
            int trans[26];
            int link, maxl;
        } t[SIZE];
    
        int root[SIZE], pos[SIZE];
    
        int tot, head[SIZE], ver[SIZE], Next[SIZE];
        void add_edge(int u, int v) {
            ver[++ tot] = v;    Next[tot] = head[u];    head[u] = tot;
        }
    
        void extend(int id, int c) {
            int p = Last,
                np = Last = ++ cT;
    
            SGT::insert(root[np], 1, n, id);
            pos[np] = id;
    
            t[np].maxl = t[p].maxl + 1;
    
            for (; p && t[p].trans[c] == 0; p = t[p].link) t[p].trans[c] = np;
    
            if (!p) {
                t[np].link = 1;
            } else {
                int q = t[p].trans[c];
    
                if (t[q].maxl == t[p].maxl + 1) {
                    t[np].link = q;
                } else {
                    int nq = ++ cT;
    
                    t[nq] = t[q], t[nq].maxl = t[p].maxl + 1, pos[nq] = pos[q];
                                    t[np].link = t[q].link = nq;
                    for (; p && t[p].trans[c] == q; p = t[p].link) t[p].trans[c] = nq;
                }
            }
        }
    
        void build_tree() {
            for (int i = 2; i <= cT; i ++)
                add_edge(t[i].link, i);
        }
    
        void dfs(int u) {
            for (int i = head[u]; i; i = Next[i]) {
                int v = ver[i];
                dfs(v);
                root[u] = SGT::merge(root[u], root[v]);
            }
        }
    
        int f[SIZE], g[SIZE];
    
        void dp(int u) {
            if (t[u].link == 1) {
                f[u] = 1, g[u] = u;
            } else if (u > 1) {
                int pa = t[u].link;
                if (SGT::ask(root[g[pa]], 1, n, pos[u] - t[u].maxl + t[g[pa]].maxl, pos[u] - 1)) {
                    f[u] = f[pa] + 1, g[u] = u;
                } else {
                    f[u] = f[pa], g[u] = g[pa];
                }
            }
    
            ans = std::max(ans, f[u]);
    
            for (int i = head[u]; i; i = Next[i]) {
                int v = ver[i];
                dp(v);
            }
        }
    }
    
    int main() {
        scanf("%d", &n);
        scanf("%s", str + 1);
    
        for (int i = 1; i <= n; i ++)
            SAM::extend(i, str[i] - 'a');
    
        SAM::build_tree();
        SAM::dfs(1);
        SAM::dp(1);
    
        printf("%d\n", ans);
    
        return 0;
    }