rt。思路是先借助 AC 自动机构建偏序关系，求传递闭包后求拆点二分图的最大匹配，转化为网络流用 Dinic 求解，然后根据最小割的必须边构造方案。交到 CF 上 WA on #3，显示是构造方案错了。想了好久没有想到错在哪了，求大佬帮忙看一下。（没时间的话如果有 #3 的数据也可以直接给我数据。）代码如下：

#include <iostream>
#include <cstring>
#include <bitset>
#include <queue>
#include <cmath>

#define st static
#define il inline
#define re register
#define rep(i, s, t) for(re int i=s; i<=t; ++i)
#define arep(i, s, t) for(re int i=s; i>=t; --i)
#define repd(i, s, t, d) for(re int i=s; i<=t; i+=d)

const int MAXN=1.5e3+3, INF=0x3f3f3f3f;

typedef std::vector<int> vec;
typedef std::string str;

namespace sol {
    int n;
    std::vector<str> S;
    std::bitset<MAXN> sub[MAXN];

    #define fail(x) to[x][2]
    #define to_(x, d) to[x][d]
    #define to(x, c) to[x][c-'a']
    class tire {
        private:
        std::vector<vec> to;
        vec F, ed, fa;
        public:
        void init() {
            return to.resize(1, vec(3, 0)), fa.resize(1, 0), F.resize(1, 0), ed.resize(n+1, 0), void();
        }
        void add(const str& s, const int k) {
            st int state; state=0;
            rep(i, 0, (int)s.length()-1) {
                if(!to(state, s[i])) to.push_back(vec(3, 0)), F.push_back(0), to(state, s[i])=to.size()-1, fa.push_back(state);
                state=to(state, s[i]);
            }
            return F[state]=k, ed[k]=state, void();
        }
        void set_fail() {
            std::queue<int> Q;
            rep(i, 0, 1) if(to_(0, i)) Q.push(to_(0, i));
            while(!Q.empty()) {
                st int u, Fail; u=Q.front(), Q.pop(), Fail=fail(u);
                rep(i, 0, 1) {
                    st int v; v=to_(u, i);
                    if(v) {
                        while(!to_(Fail, i)&&Fail) Fail=fail(Fail);
                        fail(v)=to_(Fail, i), Q.push(v);
                    }
                }
            }
            return;
        }
        void aca() {
            rep(i, 1, n) sub[i].reset();
            rep(i, 1, n) {
                for(re int state=ed[i]; state; state=fa[state]) {
                    if(state!=ed[i]&&F[state]) sub[F[state]][i]=1;
                    int& Fail=fail(state);
                    while(Fail&&!F[Fail]) Fail=fail(Fail);
                    sub[F[Fail]][i]=1;
                }
            }
            return;
        }
    }T;
    #undef to
    #undef to_
    #undef fail

    class network {
        private:
        struct E {
            int nxt, to, cap, flow;
        };
        std::vector<E> eds;
        int fir[MAXN], cur[MAXN];
        public:
        int s, t, dep[MAXN];
        void init() {
            return std::memset(fir, -1, sizeof(fir)), s=(n<<1)+1, t=s+1, eds.clear(), void();
        }
        void add(const int u, const int v, const int c) {
            return eds.push_back({fir[u], v, c, 0}), eds.push_back({fir[v], u, 0, 0}),
            fir[u]=eds.size()-2, fir[v]=eds.size()-1, void();
        }
        bool bfs() {
            std::queue<int> Q;
            Q.push(s), std::memset(dep, 0, sizeof(dep)), dep[s]=1;
            while(!Q.empty()) {
                st int u; u=Q.front(), Q.pop();
                for(re int i=fir[u]; ~i; i=eds[i].nxt) {
                    #define e eds[i]
                    #define v eds[i].to
                    if(dep[v]||e.cap<=e.flow) continue;
                    dep[v]=dep[u]+1, Q.push(v);
                    #undef e
                    #undef v
                }
            }
            return dep[t];
        }
        int dfs(const int u, const int flow) {
            if(u==t||!flow) return flow;
            re int nf=0, d;
            for(int& i=cur[u]; ~i; i=eds[i].nxt) {
                #define e eds[i]
                #define v eds[i].to
                if(dep[v]==dep[u]+1&&(d=dfs(v, std::min(flow-nf, e.cap-e.flow)))) {
                    nf+=d, e.flow+=d, eds[i^1].flow-=d;
                    if(nf==flow) return nf;
                }
                #undef e
                #undef v
            }
            if(!nf) cur[u]=-1;
            return nf;
        }
        int max_flow() {
            st int f; f=0;
            while(bfs()) {
                std::memcpy(cur, fir, sizeof(fir));
                f+=dfs(s, INF);
            }
            return f;
        }
    }net;

    il void input() {
        std::ios::sync_with_stdio(false),
        std::cin.tie(nullptr),
        std::cin >> n, T.init(), S.resize(n+1);
        rep(i, 1, n) std::cin >> S[i], T.add(S[i], i);
        return;
    }

    il void jud() {
        T.set_fail(), T.aca();
        rep(j, 1, n) rep(i, 1, n) if(sub[i][j]) sub[i]|=sub[j];
        return;
    }
    il void build_bigraph() {
        net.init();
        rep(i, 1, n) rep(j, 1, n) if(sub[i][j]) net.add(i, j+n, 1);
        rep(i, 1, n) net.add(net.s, i, 1), net.add(i+n, net.t, 1);
        return;
    }

    il void main() {
        input(), jud(), build_bigraph(), std::cout << n-net.max_flow() << '\n';
        rep(i, 1, n) if(net.dep[i]&&!net.dep[i+n]) std::cout << i << ' ';
        return;
    }
}


int main() {
    return sol::main(), 0;
}

麻烦各位了。