【Codeforces 590E】Birthday
AC 自动机，最长反链
题目大意：
给定 $n$ 个只由a,b组成的字符串，保证两两不同。
要求从中选出尽可能多的字符串，使得选出的字符串中，任意一个字符串不是另一个的子串。
求最多能选多少并输出一个可行解。
题解：
$n$ 比较小，对两个串 $s,t$，若 $t$ 被 $s$ 包含，则从 $s$ 向 $t$ 连一条有向边。这样的图一定是一张 DAG，要求的是它的最大独立集。
那么可以对所有串建 AC 自动机，然后再让每个串在 AC 自动机上跑，每个位置暴力跳 fail 并连边。
这样做的复杂度高达 $O(n\sum |s|)$，无法通过。
考虑若 $a$ 包含 $b$，$b$ 包含 $c$，则 $a$ 包含 $c$。
因此对一个点，我们没必要一直往上跳 fail，只需要判断这个点本身和往上跳到最近的一个点即可。构造 AC 自动机的时候对每个点预处理出 fail 树上最近的存在字符串的祖先，就只需判断自己和 fail 两个结点。
这样复杂度是 $O(\sum|s|)$。
现在我们得到的是一张 DAG，要求选出最多的点，使得两两间不可达。即求最长反链。
我们通过对这个图传递闭包，将任意两个可达的点之间连边。则问题又转化为最大独立集。
将 DAG 上每个点 $i$ 拆成 $x(i),y(i)$，如果 $i$ 到 $j$ 有边，则 $x(i)$ 与 $y(j)$ 之间连边。
然后求二分图最大独立集。
这里需要输出方案。
考虑求出最大匹配，我们构造最小点覆盖。
我们找到所有 $x(i)$ 满足其未被匹配。从 $x(i)$ 开始，向右走非匹配边，向左走匹配边，标记经过的点。
则左边的未被标记的点和右边的被标记的点，即为最小点覆盖。
简单地证明下：
存在三种边：
- 左右点均被标记。
- 左没被标记，右被标记。
- 左被标记，右没被标记。
对于 1，其被右边被标记的点覆盖。
对于 2，其被左边没被标记的点覆盖。
对于 3，若左端点是匹配点，则其标记只可能和它匹配的右端点来，相应地会标记它右端的点。若左端点不是匹配点，那么右端点必定是匹配点，而左端点是一条路径的起点，右端点肯定马上会被标记掉。故不存在这种情况。
所以这种构造能完全覆盖所有边。而且我们选出的结点都是最大匹配上的某一个端点，且不存在两个选出的结点有边相连，所以等于最大匹配。
取其补集即为最大独立集。
接下来要求最长反链上的点。
对于 $i$，若 $x(i)$ 和 $y(i)$ 都在最大独立集里，则 $i$ 在最长反链中，反之不在。
对于这个的证明可以参考这篇博客，我证不来就记结论了。
传递闭包和二分图匹配的复杂度均为 $O(n^3)$，常数很小，可以通过。
Code：
#include<cstdio>
#include<bitset>
#include<vector>
#include<cstring>
using namespace std;
const int M=1e7+5,N=777;
int ch[M][2],fail[M],nod,n,Len[N],ur[M];
bool*str[N];
char s[M];
bitset<N>con[N];
void insert(bool*b,int len,int id){
int nw=0;
for(int i=0;i<len;++i){
const bool c=b[i];
if(!ch[nw][c])ch[nw][c]=++nod;
nw=ch[nw][c];
}
ur[nw]=id;
}
void build_AC(){
static int q[M];int head=1,tail=0;
if(ch[0][0])q[++tail]=ch[0][0];
if(ch[0][1])q[++tail]=ch[0][1];
while(head<=tail){
int u=q[head++];
for(int c=0;c<2;++c)if(ch[u][c]){
int v=ch[u][c];
q[++tail]=v;
fail[v]=ch[fail[u]][c];
if(!ur[v])ur[v]=ur[fail[v]];
}else ch[u][c]=ch[fail[u]][c];
}
}
void match(bool*b,int len,int id){
int nw=0;
for(int i=0;i<len;++i){
bool c=b[i];
nw=ch[nw][c];
if(ur[nw])con[id].set(ur[nw]);
if(ur[fail[nw]])con[id].set(ur[fail[nw]]);
}
if(ur[nw])con[id].set(ur[nw]);
if(ur[fail[nw]])con[id].set(ur[fail[nw]]);
}
bool vis[N],bl[N][2];
int lv[N],rv[N];
bool dfs(int u){
for(int v=1;v<=n;++v)
if(!vis[v]&&con[u][v]){
vis[v]=1;
if(!lv[v]||dfs(lv[v])){
lv[v]=u;return 1;
}
}
return 0;
}
void DFS(int u){
if(!u)return;
bl[u][0]=1;
for(int i=1;i<=n;++i)
if(con[u].test(i)&&!bl[i][1]){
bl[i][1]=1;
DFS(lv[i]);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%s",s);
int len=strlen(s);
Len[i]=len;
str[i]=new bool[len+2];
for(int j=0;j<len;++j)
str[i][j]=s[j]=='b';
insert(str[i],len,i);
}
build_AC();
for(int i=1;i<=n;++i)match(str[i],Len[i],i);
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
if(con[i].test(k))
con[i]|=con[k];
for(int i=1;i<=n;++i)con[i].reset(i);
/* for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(con[i].test(j))printf("%d %d\n",i,j);
*/ memset(lv,0,sizeof lv);
for(int i=1;i<=n;++i){
memset(vis,0,sizeof vis);
dfs(i);
}
// for(int i=1;i<=n;++i)printf("%d\n",lv[i]);
for(int i=1;i<=n;++i)rv[lv[i]]=i;
vector<int>vec;
for(int i=1;i<=n;++i)if(!rv[i])DFS(i);
for(int i=1;i<=n;++i)
if(bl[i][0]&&!bl[i][1])vec.push_back(i);
printf("%u\n",vec.size());
for(int i=0;i<vec.size();++i)printf("%d ",vec[i]);
return 0;
}