题目描述
输入格式
输出格式
样例
数据范围与提示
对于全部数据,1≤n≤12,1≤∣Si∣≤50
AC自动机
一开始没看清题,以为只要最短长度。例abc bc,我想在insert时对路径+1,然后建AC时把它的fail链都-1,然后dfs统计答案。
emmm
后来还顺着错误思路想了想。然后我就不是人了…
看到数据范围,考虑下状压。(一开始居然没想到,还是年轻)
将每个Trie节点状压走到当前节点可以匹配到的字符串,可以不用预处理从父亲继承,因为bfs时是从父亲转移的。
Trie图上的匹配过程是可以不用fail指针的,因为他的son[i]已经包含了fail。如果失配(实际上没有这个son)则会接下它Trie图的son(实际fali指针)继续匹配,保证搜索最优。
我们可以考虑在Trie图上进行bfs(由’a’开始遍历,保证字典序),最早全状态即为最优解。
1 #include<cstdio> 2 #include<queue> 3 #include<algorithm> 4 #define F(i,a,b) for(i=a;i<=b;++i) 5 #define reg register 6 using namespace std; 7 struct Trie 8 { 9 Trie *son[26],*fail; 10 int cnt,bh; 11 }; 12 int tot=0,pre[2478080],stack[2478080],top; 13 bool vis[650][(1<<12)+5]; 14 char s[65]; 15 queue<Trie*> q; 16 queue<int> val,num; 17 Trie* newnode() 18 { 19 Trie *p=new Trie; 20 p->fail=NULL; p->cnt=0; p->bh=++tot; 21 reg int i; 22 F(i,0,25) p->son[i]=NULL; 23 return p; 24 } 25 void insert(Trie *root,int id) 26 { 27 Trie *p=root; reg int i=0,c; 28 while(s[++i]) 29 { 30 c=s[i]-'A'; 31 if(p->son[c]==NULL) p->son[c]=newnode(); 32 p=p->son[c]; 33 } 34 p->cnt|=1<<(id-1); 35 } 36 void AC(Trie *root) 37 { 38 Trie *p; reg int i; 39 F(i,0,25) 40 { 41 if(root->son[i]!=NULL) 42 { 43 root->son[i]->fail=root; 44 q.push(root->son[i]); 45 } 46 else root->son[i]=root; 47 } 48 while(!q.empty()) 49 { 50 p=q.front(); 51 q.pop(); 52 F(i,0,25) 53 { 54 if(p->son[i]!=NULL) 55 { 56 p->son[i]->fail=p->fail->son[i]; 57 if(p->son[i]->fail!=NULL) 58 p->son[i]->cnt|=p->son[i]->fail->cnt; 59 q.push(p->son[i]); 60 } 61 else p->son[i]=p->fail->son[i]; 62 } 63 } 64 } 65 void PT(int x) 66 { 67 if(!x) return; 68 PT(pre[x]); 69 printf("%c",stack[x]+'A'); 70 } 71 int main() 72 { 73 int n; Trie *root=newnode(); 74 scanf("%d",&n); 75 reg int i,w,id; 76 F(i,1,n) 77 { 78 scanf("%s",s+1); 79 insert(root,i); 80 } 81 AC(root); 82 // F(i,0,25) if(root->son[i]!=NULL) stack[++top]=i,pre[top]=0,q.push(root->son[i]),val.push(root->son[i]->cnt),num.push(top); 83 const int S=(1<<n)-1; 84 Trie *p; 85 q.push(root); val.push(0); num.push(0); 86 vis[root->bh][0]=1; 87 while(!q.empty()) 88 { 89 p=q.front(); 90 w=val.front(); 91 id=num.front(); 92 // printf("%d %d ",w,top); 93 q.pop(); val.pop(); num.pop(); 94 if(w==S) 95 { 96 PT(id); 97 return 0; 98 } 99 F(i,0,25) 100 { 101 if(p->son[i]!=NULL&&!vis[p->son[i]->bh][w]) 102 { 103 vis[p->son[i]->bh][w|p->son[i]->cnt]=1; 104 stack[++top]=i; 105 pre[top]=id; 106 q.push(p->son[i]); 107 val.push(w|p->son[i]->cnt); 108 num.push(top); 109 } 110 } 111 } 112 return 0; 113 }