本文共 644 字，大约阅读时间需要 2 分钟。

正题

题目链接:

题目大意

$n$个字符串，求一个最大的集合使其中没有任何串是其他集合内字符串的子串

解题思路

先用$AC$自动机建立好$fail$树+传递闭包就可以确定好两两之间的子串关系了，之后用网络流最大匹配求最大独立集即可

$code$

#pragma GCC optimize(2)%:pragma GCC optimize(3)%:pragma GCC optimize("Ofast")%:pragma GCC optimize("inline")#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int N=1e7+10,M=1600,inf=2147483647/3;struct node{
   	int to,next,w;}a[1010000];int n,tot=1,cnt,s,t;int ch[N][2],fail[N],fa[N],cur[M];int ls[M],ed[N],pos[N],dep[M];bool d[M][M];char st[N];queue
       
         q;void Make(char *s,int num){
   	int x=1,len=strlen(s);	for(int i=0;i
       
      
     
    
   

转载地址：http://ycwaf.baihongyu.com/