题解 CF590E 【Birthday】

· · 题解

CF590E Birthday

建出AC自动机.

考虑建出字符串之间的包含关系图.

因为\sum\limits_{i=1}^n |s_i| \leq 10^7,所以我们不能在AC自动机上暴力跳,而是在AC自动机上用并查集维护fail树上的上一个点,然后暴力跳trie树上的父亲直到跳到一个存在的字符串即可.

然后O(n^3)把多余的边建出来,直接求最长反链方案即可.

最长反链方案怎么求?

建出拆点二分图并求出其最大匹配.

考虑求出拆点二分图的最大独立集,具体操作是:

从每个没有匹配的左部点开始dfs,

左->右的边只走没有匹配的边,

右->左的边只走匹配的边,

然后所有dfs到的左部点和未dfs到的右部点就组成了最大独立集.

然后,左右都在最大独立集里的点i就在最长反链里.

O(n^3+\sum\limits_{i=1}^n |s_i|).

代码:

#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &x){
    x = 0; int f = 1; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();}
    x *= f;
}
inline void write(int x){if (x > 9) write(x/10); putchar(x%10+'0'); }

const int V = 10000005,N = 760;

int n; bool G[N][N];

char s[V];
struct Trie{
    int ch[V][2],id[V],cnt,pos[N],fa[V];
    inline void Insert(char *s,int n,int Id){
        int now = 1,i,c;
        for (i = 0; i < n; ++i,now = ch[now][c])
            if (!ch[now][c=s[i]-'a']){ ch[now][c] = ++cnt; fa[cnt] = now; }
        id[now] = Id; pos[Id] = now;
    }
    queue<int>q; int fail[V];
    inline void buildfail(){
        int x; fail[1] = 1;
        if (ch[1][0]) fail[ch[1][0]] = 1,q.push(ch[1][0]); else ch[1][0] = 1;
        if (ch[1][1]) fail[ch[1][1]] = 1,q.push(ch[1][1]); else ch[1][1] = 1;
        while (!q.empty()){
            x = q.front(),q.pop();
            if (ch[x][0]) fail[ch[x][0]] = ch[fail[x]][0],q.push(ch[x][0]); else ch[x][0] = ch[fail[x]][0];
            if (ch[x][1]) fail[ch[x][1]] = ch[fail[x]][1],q.push(ch[x][1]); else ch[x][1] = ch[fail[x]][1];
        }
    }
    int tfa[V];
    inline int Find(int x){ return x == tfa[x] ? x : (tfa[x] = Find(tfa[x])); }
    inline void buildtrans(){
        int i,x;
        for (i = 1; i <= cnt; ++i) tfa[i] = id[i] ? i : fail[i];
        for (i = 1; i <= n; ++i){
            x = pos[i];
            if (id[Find(fail[x])]) G[i][id[Find(fail[x])]] = 1; 
            x = fa[pos[i]];
            while (x){
                if (id[x]){ G[i][id[x]] = 1; break; }
                if (id[Find(x)]) G[i][id[Find(x)]] = 1; 
                x = fa[x];
            }
        }
    }
}T;

int match[N];
int match2[N]; 
bool vis[N];
inline int Find(int x){
    if (vis[x]) return 0; vis[x] = 1;
    for (int i = 1; i <= n; ++i) if (G[x][i] && (!match[i] || Find(match[i]))){
        match[i] = x; return 1;
    }
    return 0;
}
bool vis1[N],vis2[N];
inline void dfs(int x){
    if (vis1[x]) return; vis1[x] = 1; 
    for (int i = 1; i <= n; ++i) if (G[x][i] && match2[x] != i && !vis2[i]){
        vis2[i] = 1; if (match[i]) dfs(match[i]);
    } 
}

int ans[N],lans;
int main(){
    register int i,j,k;
    scanf("%d",&n);
    for (T.cnt = i = 1; i <= n; ++i) scanf("%s",s),T.Insert(s,strlen(s),i); 
    T.buildfail(); T.buildtrans();
    for (k = 1; k <= n; ++k) for (i = 1; i <= n; ++i) for (j = 1; j <= n; ++j) G[i][j] |= G[i][k] && G[k][j];
    for (i = 1; i <= n; ++i) memset(vis,0,n+1),Find(i);
    for (i = 1; i <= n; ++i) if (match[i]) match2[match[i]] = i;
    for (i = 1; i <= n; ++i) if (!match2[i]) dfs(i);
    for (i = 1; i <= n; ++i) if (vis1[i] && !vis2[i]) ans[++lans] = i;
    printf("%d\n",lans);
    for (i = 1; i <= lans; ++i) printf("%d ",ans[i]);
    puts("");
    return 0;
}