solution-p8368 [LNOI2022] 串

· · 题解

T4

Description

给定一个英文小写字母构成的字符串 S，你需要找到一个尽可能长的字符串序列 (T_0, T_1, \ldots, T_l)，满足：

输出这样的字符串序列的长度的最大值（即 l 的最大值）。

Solution

一个思路很清奇的题目，乍一看以为和19年省选的那个字符串问题差不多，其实完全没关系。

观察一下这个字符串序列，逆向去想一下，可以这么构造：[i,j]\rightarrow [i-1,j-2]\rightarrow [i-2,j-4]... 一直这样下去直到长度为 0 或者到头了。那么答案就有一个显然的下界 \lfloor n/2\rfloor。

然后上面这个构造的瓶颈在于走到头就没得走了，我们需要考虑什么时候可以往后跳回去。

然后就是比较重要的性质了：一个串可以往回跳的充要条件是出现了至少两次。

假设出现位置是 [i_1,j_1],[i_2,j_2](i_1<i_2)，那么我们从 [i_2,j_2] 开始，按照上述的构造方法构造，当左端点到 i_1 时，我们跳回到 i_2 即可。

反过来的话就是如果只出现一次，那么这个串对应的 S_i' 是唯一的，别的跳不回来。

这样就很简单了，如果可以往回跳那么我们从 [i_2,j_2] 开始一路跳就可以跳到长度为 0。

对于一个出现至少两次的串 [l,r]，若选择它作为跳的开始，答案为 r-l+1+\lfloor(n-r)/2\rfloor。

我们求出以每个下标为右端点的最长的出现至少两次的串，取个 max。

这个事情用 SAM 搞一搞就可以做，就对于每个节点记录最靠左的位置和 siz 就好了。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

namespace solve
{
    const int maxn = 2e6 + 10;

    int n;

    struct SAM
    {
        int mx[maxn], siz[maxn], ch[maxn][26], father[maxn], pos[maxn];
        int lst, tot;
        int ans;
        void insert(int c, int id)
        {
            int p = ++tot, f = lst;
            siz[p] = 1, mx[p] = mx[f] + 1, lst = p, pos[p] = id;
            while (f && !ch[f][c])
                ch[f][c] = p, f = father[f];
            if (!f)
                father[p] = 1;
            else
            {
                int q = ch[f][c];
                if (mx[q] == mx[f] + 1)
                    father[p] = q;
                else
                {
                    int nq = ++tot;
                    memcpy(ch[nq], ch[q], sizeof(ch[q])), father[nq] = father[q], mx[nq] = mx[f] + 1;
                    pos[nq] = n + 1;
                    father[p] = father[q] = nq;
                    while (f && ch[f][c] == q)
                        ch[f][c] = nq, f = father[f];
                }
            }    
        }
        vector<int> e[maxn];
        void build()
        {
            for (int i = 2; i <= tot; i++)
                e[father[i]].push_back(i);
        }
        void dfs(int x)
        {
            for (int v : e[x])
            {
                dfs(v);
                siz[x] += siz[v], pos[x] = min(pos[x], pos[v]);
            }
            if (siz[x] > 1)
                ans = max(ans, (n - pos[x]) / 2 + mx[x]);
        }
        void clear()
        {
            for (int i = 1; i <= tot; i++)
                e[i].clear(), memset(ch[i], 0, sizeof(ch[i]));
            memset(father, 0, sizeof(int) * (tot + 4));
            memset(mx, 0, sizeof(int) * (tot + 4));
            memset(siz, 0, sizeof(int) * (tot + 4));
            memset(pos, 0, sizeof(int) * (tot + 4));
            lst = tot = 1;
            ans = 0;
        }
        SAM() { lst = tot = 1; }
    } sam;

    char s[maxn];

    void main()
    {
        cin >> s;
        n = strlen(s);
        for (int i = 0; i < n; i++)
            sam.insert(s[i] - 'a', i + 1);
        sam.build(), sam.dfs(1);
        cout << max(sam.ans, n / 2) << endl;
        sam.clear();
    }
}

int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--)
        solve::main();
}