LNOI2022省选串题解

串串构造题，纪念自己做出来的黑串串构造。大胆猜想！小心求证。

以下定义$n=|S|$。

我们首先根据题目中给出的第三个条件，我们来看子串$S$ 在放进$T_{i}$ 和$T_{i-1}$ 的形式是怎么样的：

那么，由图不难观察到一个很明显的构造过程，也就是我们先反过来，由$[l,r]$ 出发，右端点每一次减小 2，左端点每一次减小 1，也就是$[l,r] \to [l-1,r-2]\to [l-2,r-4] \dots [l-x,r-2x]$。那么有一个显然的移动下界就是在极端情况下$[l,r]=[1,n]$，最多只能移动$\dfrac{n}{2}$ 次。那么现在问题在于如何使得这个移动过程能够足够移动多次，首先根据题意不难得出对于每一个$T_{i}$ 都要保证是$S$ 的子串，而且我们还要每次从上一个$T_{i-1}$ 转移过来，也就是说，对全局起决定性作用的在于$T_{0}$ 的选取，我们怎么选取才能最好呢？

哎，我有一计！$T_{0}$ 是子串，子串又没有说非空子串，那我选空子串，那么后面的操作相当于就是找长度为 1 的子串，找长度为 2 的子串，以此类推下去。证明当$T_{0}$ 是空串时存在最优解是显然的。

但是我们上面还有一个前后缀的性质，也就是说$T_{i}$ 由$T_{i-1}$ 加一个字符过来，并且还要求是一个原字符串一个子串的前后缀，那什么情况下能满足加一个字符是子串的前后缀呢？我们从我们选取的子串下手：

只能加一个字符，那么也就是说如果$S$ 选一个前缀加一个字符放到后面拼后缀还能和原来重合？那么，也就是说，这个我们构造的串至少要在$S$ 种出现两次这样的话我们才能扩大区间，感性理解就是如果不这样的话你转移到$T_{i}$ 前后缀都覆盖不了啊，是无法满足的，严谨证明可以考虑反证法。

那么有两个这个结论，我们找一个至少出现两次的子串$[l,r]$，那么首先区间能拓展$r-l+1$，右端点每次跳两步也就是说还有$\dfrac{n-r}{2}$，那么答案就是$r-l+1 + \dfrac{n-r}{2}$。这个我们用 SAM 和 SA 可以轻松维护的，我用 SAM 因为维护至少出现两次很简单的。

注意一下，答案下界是$\dfrac{n}{2}$，可能存在没有任何拓展的情况，所以最后结果是$\max(\dfrac{n}{2},ans)$。代码其实很好写，也是我见过为数不多好写的黑题了 www。

#define ll long long
using namespace std;
constexpr int MN=1e6+15;
int n;
ll ans;
string s;

struct SAM{
    int nxt[MN][26],fa[MN],len[MN],cnt[MN],pos[MN],mnpos[MN],tot,lst;
    vector<int> adj[MN];


    int newnode(){
        int cur=++tot;
        mnpos[cur]=1e9;
        fa[cur]=len[cur]=cnt[cur]=0;
        adj[cur].clear();
        memset(nxt[cur],0,sizeof(nxt[cur]));
        return cur;
    }

    void init(){
        tot=lst=0;
        tot=lst=newnode();
    }

    int clone(int from){
        int cur=newnode();
        fa[cur]=fa[from];
        memcpy(nxt[cur],nxt[from],sizeof(nxt[from]));
        return cur;
    }

    void expand(int c){
        int cur=newnode();
        len[cur]=len[lst]+1;
        int p=lst;
        while(p&&!nxt[p][c]) nxt[p][c]=cur,p=fa[p];
        if(!p){
            fa[cur]=1;
        }else{
            int q=nxt[p][c];
            if(len[q]==len[p]+1){
                fa[cur]=q;
            }else{
                int nq=clone(q);
                len[nq]=len[p]+1;
                fa[q]=fa[cur]=nq;
                while(p&&nxt[p][c]==q) nxt[p][c]=nq,p=fa[p];
            }
        }
        lst=cur;
    }

    void inittree(){
        for(int i=2;i<=tot;i++){
            adj[fa[i]].push_back(i);
        }
    }

    void dfs(int u){
        for(auto v:adj[u]){
            dfs(v);
            cnt[u]+=cnt[v];
            mnpos[u]=min(mnpos[u],mnpos[v]);
        }
        if(cnt[u]>=2){
            ans=max(ans,1ll*len[u]+(n-mnpos[u])/2);
        }
    }

}sam;

void init(){
    sam.init();
}

void solve(){
    init();
    cin>>s;
    n=s.length();
    s=" "+s;
    for(int i=1;i<=n;i++){
        sam.expand(s[i]-'a');
        sam.cnt[sam.lst]++;
        sam.mnpos[sam.lst]=i;
    }
    sam.inittree();
    ans=n/2;
    sam.dfs(1);
    cout<<ans<<'\n';
}

int main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }

    return 0;
}