题目分析
题意
给定 \(n\) 个字符串，要求从中选出若干个组成一个集合，且集合中每个字符串都互不包含。
求集合最大包含几个字符串。
分析
本题弱化版：[ABC354G] Select Strings
就是求一个最长反链，并求构造方案。
求构造方案还是比较有意思的。
建议先做 P4298 [CTSC2008] 祭祀。
一开始用的 KMP 暴力匹配字符串。
然后：
\(n \le 750\)，\(\sum_{i=1}^n \limits |s_i| \le 10^7\)。
KMP 直接 TLE on #64。
KMP 挂了，考虑上 AC 自动机。
建好 fail 指针后考虑从串的末尾节点跳 fail，每跳一次判断到根的路径上有无结尾标记，进而判断包含关系。
然而一次判断就是 \(O(\sum|s_i|)\)，同样 TLE。
我们可以标记跳 fail 的路径，然后模拟插入串的过程。
如果遇到有标记的节点，那么就向标记它的节点连边。
因为我们最后会用 floyd 传递闭包，所以标记跳 fail 的路径直接覆盖标记即可。
这样就能 \(O(\sum|s_i|)\) 完成建图。
总时间复杂度 \(O(\sum|s_i| + n^3)\)。
Code
#include<bits/stdc++.h>
using namespace std;
template<typename Tp, size_t sizn, size_t sizm>
struct netflow
{
int cnt=1, s=sizn-2, t=sizn-3;
Tp val[sizm<<1], dis[sizn];
void link(int u, int v, Tp w)
{
// println(cerr, "{} {} {}", u, v, w);
to[++cnt]=v; val[cnt]=w;
nxt[cnt]=head[u]; head[u]=cnt;
to[++cnt]=u; val[cnt]=0;
nxt[cnt]=head[v]; head[v]=cnt;
}
int head[sizn], to[sizm<<1], nxt[sizm<<1], now[sizm<<1];
Tp inf=numeric_limits<Tp>::max()/2;
int bfs()
{
for(int i=1;i<sizn;i++) dis[i]=inf;
dis[t]=inf;
queue<int> q;
q.push(s);
dis[s]=0;
now[s]=head[s];
while(!q.empty())
{
int idx=q.front(); q.pop();
for(int i=head[idx];i;i=nxt[i])
{
int arr=to[i];
if(val[i]>0&&dis[arr]==inf)
{
q.push(arr);
now[arr]=head[arr];
dis[arr]=dis[idx]+1;
if(arr==t) return 1;
}
}
}
return 0;
}
Tp dfs(int idx, Tp sum)
{
if(idx==t) return sum;
Tp k, res=0;
for(int i=now[idx];i&∑i=nxt[i])
{
now[idx]=i;
int arr=to[i];
if(val[i]>0&&(dis[arr]==dis[idx]+1))
{
k=dfs(arr, min(sum, val[i]));
if(k==0) dis[arr]=inf;
val[i]-=k; res+=k;
val[i^1]+=k; sum-=k;
}
}
return res;
}
Tp maxflow()
{
Tp ans=0;
while(bfs()) ans+=dfs(s, inf);
return ans;
}
};
netflow<int, 100005, 1000005> nf;
#define maxn 10000007
#define maxm 802
#define l(x) ((x)<<1)
#define r(x) ((x)<<1|1)
namespace AC
{
int ch[maxn][2], fail[maxn], flg[maxn];
int siz=0;
void insert(string m, int idx)
{
int now=0;
for(auto i:m)
{
if(!ch[now][i-'a'])
ch[now][i-'a']=++siz;
now=ch[now][i-'a'];
}
flg[now]=idx;
}
void build_fail()
{
queue<int> q;
for(int i=0;i<2;i++)
if(ch[0][i])
q.push(ch[0][i]);
while (!q.empty())
{
int now=q.front();
q.pop();
for(int i=0;i<2;i++)
if(ch[now][i])
{
int v=ch[now][i];
fail[v]=ch[fail[now]][i];
if(!flg[v])
flg[v]=flg[fail[v]];
q.push(v);
}
else ch[now][i]=ch[fail[now]][i];
}
}
};
string ss[maxm];
int tag[maxm<<1];
bitset<maxm> bs[maxm];
void dfs(int u)
{
tag[u]=1;
for(int i=nf.head[u];i;i=nf.nxt[i])
{
int v=nf.to[i];
if(v!=nf.t&&v!=nf.s&&nf.val[i]&&!tag[v])
dfs(v);
}
}
void search(int i)
{
int u=0;
for(auto c:ss[i])
{
if(AC::flg[u]&&AC::flg[u]!=i)
bs[i][AC::flg[u]]=1;
u=AC::ch[u][c-'a'];
}
if(AC::flg[AC::fail[u]]&&AC::flg[AC::fail[u]]!=i)
bs[i][AC::flg[AC::fail[u]]]=1;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>ss[i];
AC::insert(ss[i], i);
}
AC::build_fail();
for(int i=1;i<=n;i++) search(i);
for(int j=1;j<=n;j++)
for(int i=1;i<=n;i++)
if(bs[i][j])
bs[i]|=bs[j];
for(int j=1;j<=n;j++)
for(int i=1;i<=n;i++)
if(bs[i][j]) nf.link(l(i), r(j), nf.inf);
for(int i=1;i<=n;i++)
{
nf.link(nf.s, l(i), 1);
nf.link(r(i), nf.t, 1);
}
int ret=nf.maxflow();
cout<<(n-ret)<<'\n';
for(int i=nf.head[nf.s];i;i=nf.nxt[i])
if(nf.val[i]) dfs(nf.to[i]);
for(int i=1;i<=n;i++)
if(tag[l(i)]&&!tag[r(i)]) cout<<i<<' ';
}