建出(AC)自动机(.)
考虑建出字符串之间的包含关系图(.)
因为(sumlimits_{i=1}^n |s_i| leq 10^7,)所以我们不能在(AC)自动机上暴力跳(,)而是在(AC)自动机上用并查集维护(fail)树上的上一个点(,)然后暴力跳(trie)树上的父亲直到跳到一个存在的字符串即可(.)
然后(O(n^3))把多余的边建出来(,)直接求最长反链方案即可(.)
最长反链方案怎么求(?)
建出拆点二分图并求出其最大匹配(.)
考虑求出拆点二分图的最大独立集(,)具体操作是(:)
从每个没有匹配的左部点开始(dfs,)
左->右的边只走没有匹配的边(,)
右->左的边只走匹配的边(,)
然后所有(dfs)到的左部点和未(dfs)到的右部点就组成了最大独立集(.)
然后(,)左右都在最大独立集里的点(i)就在最长反链里(.)
(O(n^3+sumlimits_{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]);
if (ch[1][1]) fail[ch[1][1]] = 1,q.push(ch[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
",lans);
for (i = 1; i <= lans; ++i) printf("%d ",ans[i]);
puts("");
return 0;
}