浪费了我一晚上的生命…

Solution

关于本题有两种做法，我一开始写的第一种：建立广义SAM，统计parent树上的endpos集合是否可以包含所有的字符串，如果可以就用len更新ans。可以状压。

做法我拍了一下，大概是没问题的。但是这沙雕题卡常200ms我硬是给卡了一晚上😂然后发现一些神奇的问题。比如广义SAM是没法用基数排序来确定树上拓扑序的，所以得队列硬上，可惜不管怎么写都卡不过200ms。

另一种做法就是神奇的转移：先建一个串，然后对于后加入的每个串计算一下状态匹配的最大值（可以通过后缀链接上传），然后再对于每个串取个最小值，最后总体取个最大值。这样的做法基本上是常数很小的 $O(n)$ ，或者是我常数制造机了…

Code - 80ms

// Code by ajcxsu
// Problem: LCS2
#include<bits/stdc++.h>
using namespace std;

const int N=2e6+5;
int len[N], fa[N], ch[N][26];
int lst=1, idx=1;
inline void add(int c) {
    int p=lst, np=lst=++idx; len[np]=len[p]+1;
    for(; p && !ch[p][c]; p=fa[p]) ch[p][c]=np;
    if(!p) fa[np]=1;
    else {
        int q=ch[p][c];
        if(len[q]==len[p]+1) fa[np]=q;
        else {
            int nq=++idx; for(int i=0; i<26; i++) ch[nq][i]=ch[q][i];
            fa[nq]=fa[q];
            len[nq]=len[p]+1, fa[q]=fa[np]=nq;
            for(; p && ch[p][c]==q; p=fa[p]) ch[p][c]=nq;
        }
    }
}

int qu[N], h, t;
char str[N];
int bu[N], id[N];
int su[N], f[N];
void solve() {
    int x=1, l=0;
    memset(su, 0, sizeof(su));
    for(char *p=str; *p; p++) {
        if(ch[x][*p-'a']) l++, x=ch[x][*p-'a'];
        else {
            while(x && !ch[x][*p-'a']) x=fa[x];
            if(!x) l=0, x=1;
            else l=len[x]+1, x=ch[x][*p-'a'];
        }
        su[x]=max(su[x], l);
    }
    for(int i=idx; i>=1; i--) su[fa[id[i]]]=max(su[fa[id[i]]], su[id[i]]);
    for(int i=1; i<=idx; i++) len[i]=min(len[i], su[i]);
}

int main() {
    scanf("%s", str);
    for(char *p=str; *p; p++) add(*p-'a');
    for(int i=1; i<=idx; i++) bu[len[i]]++;
    for(int i=1; i<=idx; i++) bu[i]+=bu[i-1];
    for(int i=idx; i>=1; i--) id[bu[len[i]]--]=i;
    while(scanf("%s", str)==1) solve();
    int ans=0;
    for(int i=1; i<=idx; i++) ans=max(ans, len[i]);
    printf("%d\n", ans);
    return 0;
}

Code - TLE

// Code by ajcxsu
// Problem: LCS2

#include<bits/stdc++.h>
using namespace std;

const int N=2e6+5;
int len[N], fa[N], ch[N][26], in[N];
int f[N], lst=1, idx=1;
inline void add(int c, int val) {
    int p=lst, np=lst=++idx; len[np]=len[p]+1;
    f[np]=1<<val;
    for(; p && !ch[p][c]; p=fa[p]) ch[p][c]=np;
    if(!p) fa[np]=1;
    else {
        int q=ch[p][c];
        if(len[q]==len[p]+1) fa[np]=q;
        else {
            int nq=++idx; for(int i=0; i<26; i++) ch[nq][i]=ch[q][i];
            fa[nq]=fa[q], f[nq]=f[q];
            len[nq]=len[p]+1, fa[q]=fa[np]=nq;
            for(; p && ch[p][c]==q; p=fa[p]) ch[p][c]=nq;
        }
    }
}

int qu[N], h, t;
char str[N];
int main() {
    int nidx=0;
    while(scanf("%s", str)==1) {
        lst=1;
        for(char *p=str; *p; p++) add(*p-'a', nidx);
        ++nidx;
    }
    nidx=(1<<nidx)-1;
    int ans=0, na, nf;
    for(int i=1; i<=idx; i++) in[fa[i]]++;
    for(int i=1; i<=idx; i++) if(!in[i]) qu[t++]=i;
    while(h!=t) {
        na=qu[h++], nf=fa[na];
        if(f[na]==nidx && len[na]>ans) ans=len[na];
        f[nf]|=f[na], in[nf]--;
        if(!in[nf]) qu[t++]=nf;
    }
    printf("%d\n", ans);
    return 0;
}