题意
给定 \(n\) 个只由 \(a,b\) 组成的字符串，保证两两不同。
要求从中选出尽可能多的字符串，使得选出的字符串中，任意一个字符串不是另一个的子串。
求最多能选多少并输出一个可行解。
\(n \leq 750, \sum |S_i| \leq 10^6\)
思路
考虑根据包含关系建边，可以得到一张有向无环图，之后我们要求的是一个最大点集，两两不能到达。这就是祭祀。
即求最长反链，然后转化为最小链覆盖，再到传递闭包后的最大匹配，关于证明，ta没了。
接着来说一下如何输出方案。
在求完传递闭包之后，能互相到达的点一定是相邻的，所以最长反链即为最大独立集。
定义：最小点覆盖就是选择最少的点来覆盖所有的边。一个点能覆盖以它为端点的边
最大独立集=所有顶点数-最小点覆盖
突然写不下去了，就看这个吧偷懒，啥时候空了我来补
然后来考虑怎么建图。
由于是子串问题，很容易想到用AC自动机。
但是如果把所有包含关系都求出来，妥妥的T了
对于三个串 \(a,b,c\)，如果 \(a\)包含\(b\) , \(b\)包含\(c\), 那么\(a\)包含\(c\)。
回忆AC自动机匹配的过程，对于文本串\(i\)每匹配到一个字符位置\(u\)就跳\(fail\),考虑到每次第一个跳到的一定是最长的，且每次跳的都是前面所有的子串，所以我们只要将\(i\)与\(fail[u]\)上包含的最长完整串连边就行。注意\(fail[u]\)上可能不存在完整串末尾节点，那么我们就继承离他最近的\(fail\)树祖先上的串。
不要忘记\(u\)本身是末尾节点的情况。
至于怎么继承，只要在\(get \_ fail\)中加一句就好了
#include <bits/stdc++.h>
using std::string;
using std::queue;
queue <int> q;
const int N=755,M=10000005;
string s[N];
int ch[M][2],val[M],fail[M],cnt,n,vis[N],now,to[N],len[N],f[N];
int tagl[N],tagr[N];
bool a[N][N];
void insert(string s,int l,int id){
int u=0;
for (int i=0;i<l;i++){
int c=s[i]-'a';
if (!ch[u][c]) ch[u][c]=++cnt;
u=ch[u][c];
}
val[u]=id;
}
void get_fail(){
if (ch[0][0]) q.push(ch[0][0]);
if (ch[0][1]) q.push(ch[0][1]);
while (!q.empty()){
int x=q.front();
if (!val[x]) val[x]=val[fail[x]];
q.pop();
for (int i=0;i<2;i++)
if (ch[x][i]) {
q.push(ch[x][i]);
fail[ch[x][i]]=ch[fail[x]][i];
}else ch[x][i]=ch[fail[x]][i];
}
}
void match(string s,int l,int id){
int u=0;
for (int i=0;i<l;i++){
int c=s[i]-'a';
u=ch[u][c];
if (val[u]) a[id][val[u]]=1;
if (val[fail[u]]) a[id][val[fail[u]]]=1;
}
}
int dfs(int x){
for (int i=1;i<=n;i++)
if (a[x][i] && vis[i]!=now){
vis[i]=now;
if (f[i]==0 || dfs(f[i])){
to[x]=i,f[i]=x;
return 1;
}
}
return 0;
}
void dfs2(int x){
tagl[x]=1;
for (int i=1;i<=n;i++){
if (a[x][i]==0) continue;
if (!tagr[i]){
tagr[i]=1;
dfs2(f[i]);
}
}
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++){
std::cin>>s[i];
len[i]=s[i].length();
insert(s[i],len[i],i);
}
get_fail();
for (int i=1;i<=n;i++)
match(s[i],len[i],i);
for (int k=1;k<=n;k++)
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
a[i][j]=a[i][j]|(a[i][k] & a[k][j]);
for (int i=1;i<=n;i++) a[i][i]=0;
int ans=0;
for (int i=1;i<=n;i++)
now=i,ans+=dfs(i);
printf("%d\n",n-ans);
for (int i=1;i<=n;i++)
if (!to[i]) dfs2(i);
for (int i=1;i<=n;i++)
if (tagr[i]==0 && tagl[i]) printf("%d ",i);
}
后记
追随神仙的脚步
争取做到\(\frac{1}{1 page}\)